Nearest Neighbor

Time limit: 5000ms
Memory limit: 256mb

Description:
Given a set S of points in the plane and a query point q, find in S the point that is nearest to q. Here, given two points (x1, y1) and (x2, y2), their distance is defined as (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2).

Input:
The first line shows the coordinate of the query point q. The second line shows the number of points in S, followed by |S| lines with each row being a point. It is guaranteed that 1 <= |S| <= 10000 and for each coordinate (x, y) in the input, x and y are both integers in the range [-10000, 10000].

Output:
Output the coordinate of the point that is nearest to the query point. It is guaranteed that the result is unique.

Sample input:
0 0
2
-1 -1
-5 1

Sample output:
-1 -1

Explanation of the sample:
The distance between point (-1, -1) with the query point (0, 0) is (-1 - 0) * (-1 - 0) + (-1 - 0) * (-1 - 0) = 2, while the distance between (-5, 1) and (0, 0) is 26. Therefore, (-1, -1) is returned as the answer.

Submit