Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Object Detection

By ishtupeed · Limits 1s, 512 MB

Object detection is a computer vision technique that is used to identify and locate objects in an image. An image can be considered as a 2D array containing PP rows and QQ columns. Each element at position (i,j)(i, j) in the image is called a ‘picture element’ or pixel. In this problem, we will only consider Grayscale Images, which means, each pixel can be described by a single value denoting the intensity (amount of light) of that pixel. Let’s denote a N×MN\times M sub-image (where 1NP1\leq N \leq P and 1MQ1 \leq M \leq Q) of the image to be a rectangle in the image containing NN rows and MM columns.

You will be given an image containing RR rows and CC columns, and an object image containing XX rows and YY columns (XR,YC)(X \leq R, \, Y \leq C). Your task is to find out an X×YX\times Y sub-image of the given image that has the smallest distance from the object image. To calculate the distance, you need to sum up the squared difference between the intensity of each pixel of the object image and its corresponding pixel in the sub-image. For the sub-image positioned at iith row and jjth column of the original image, we can calculate the distance using:

Distanceij=p=0x1q=0y1(A(i+p)(j+q)B(p+1)(q+1))2\text{Distance}_{ij} = \sum\limits_{p=0}^{x-1}\sum\limits_{q=0}^{y-1}\left(A_{(i+p)(j+q)}-B_{(p+1)(q+1)}\right)^2,

where AA is the original image and BB is the object that we are looking for.

Input

The first line of the input contains a single integer T(1T5)T (1 \leq T \leq 5), denoting the number of test cases.

The following line contains two space-separated integers RR and C(1R,C500)C (1 \leq R, \, C \leq 500), denoting the number of rows and the number of columns in the original image, respectively. The following RR lines each contain CC space-separated integers, describing each pixel’s intensity in the original image.

The next line contains two space-separated integers X(1XR)X (1 \leq X \leq R) and Y(1YC)Y (1 \leq Y \leq C), denoting the number of rows and the number of columns in the object image, respectively. The following XX lines each contain YY space-separated integers, describing each pixel’s intensity in the object image.

The intensity value of each pixel will be in the range [0,50][0, 50].

Output

Print two space-separated integers xyx \, \, y denoting the index of the top-left corner of the sub-image that meets the criteria. If there are multiple grids with the smallest distance, print the lexicographically smallest xyx \, \, y. That means if there are multiple grids that meet the criteria, print the one with the smallest xx. If there are multiple grids with the smallest xx that meet the criteria, print the one with the smallest yy.

Assume that the indices are 1-indexed.

Sample

InputOutput
1
3 3
1 2 3
4 4 5
6 7 8
1 1
4
2 1

Discussion

Statistics


50% Solution Ratio

BigBagEarliest, 3w ago

BigBagFastest, 0.4s

BigBagLightest, 14 MB

BigBagShortest, 6777B

Submit

Login to submit

Editorial

For each X×YX\times YX×Y sub-image in the original image, we have to calculate (x−y)2=x2−2xy+y2(x-y)...

Toph uses cookies. By continuing you agree to our Cookie Policy.