There are N students and M checkpoints on the xy-plane. The coordinates of the i-th…
- User
There are N students and M checkpoints on the xy-plane. The coordinates of the i-th student (1 \leq i \leq N) is (a_i,b_i), and the coordinates of the checkpoint numbered j (1 \leq j \leq M) is (c_j,d_j). When the teacher gives a signal, each student has to go to the nearest checkpoint measured in Manhattan distance. The Manhattan distance between two points (x_1,y_1) and (x_2,y_2) is |x_1-x_2|+|y_1-y_2|. Here, |x| denotes the absolute value of x. If there are multiple nearest checkpoints for a student, he/she will select the checkpoint with the smallest index. Which checkpoint will each student go to?
Constraints
- 1 \leq N,M \leq 50
- -10^8 \leq a_i,b_i,c_j,d_j \leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 b_1 : a_N b_N c_1 d_1 : c_M d_M
Output
Print N lines. The i-th line (1 \leq i \leq N) should contain the index of the checkpoint for the i-th student to go.
Examples
Input
2 2 2 0 0 0 -1 0 1 0
Output
2 1
Input
3 4 10 10 -10 -10 3 3 1 2 2 3 3 5 3 5
Output
3 1 2
Input
5 5 -100000000 -100000000 -100000000 100000000 100000000 -100000000 100000000 100000000 0 0 0 0 100000000 100000000 100000000 -100000000 -100000000 100000000 -100000000 -100000000
Output
5 4 3 2 1
Assistant
We need to solve a problem: Given N student coordinates (a_i,b_i), M checkpoint coordinates (c_j,d_j). For each student, find the checkpoint with minimal Manhattan distance. If multiple have same distance, choose the one with smallest index.
Constraints N,M <= 50, so O(N*M) is trivial.
We need to read input and output.
But we need to implement solution.
Edge cases: distances can be large (up to 2e8), but within 64-bit.
Implementation: for each student, loop over checkpoints, compute Manhattan distance, keep track of min distance and min index. If distance < min_dist, update; if distance == min_dist and index < min_index, update.
Output the index of the chosen checkpoint (1-indexed).
That's it.
We should provide Python code.
But note: the problem expects output as lines with checkpoint indices. So implement in Python.
Given that it's a typical AtCoder problem ABC111 B? Actually it's from AtCoder Beginner Contest 057 B? Check: "Checkpoints" problem from ABC 057 B? Let's check: ABC 057 B - Checkpoints? Actually ABC 057 B is "Checkpoints" where N and M up to 50, similar description. Yes.
So solution is straightforward.
We need to ensure reading input correctly.
We'll write:
def main(): import sys input = sys.stdin.readline N, M = map(int, input().split()) students = [tuple(map(int, input().split())) for _ in range(N)] checkpoints = [tuple(map(int, input().split())) for _ in range(M)] for a,b in students: min_dist = None min_idx = None for j, (c,d) in enumerate(checkpoints, start=1): dist = abs(a-c) + abs(b-d) if min_dist is None or dist < min_dist or (dist == min_dist and j < min_idx): min_dist = dist min_idx = j print(min_idx)
if name == 'main': main()
That's all.
But as ChatGPT, we need to produce a final answer: The solution explanation and code.
Given the instructions: The assistant should provide the solution.
Thus final response: Explanation and code.
I'll output the code.
But ensure to follow typical format.
I'll produce:
import sys def main(): input = sys.stdin.readline N, M = map(int, input().split()) students = [tuple(map(int, input().split())) for _ in range(N)] checkpoints = [tuple(map(int, input().split())) for _ in range(M)] for ax, ay in students: best = 0 best_dist = 10**18 for idx, (cx, cy) in enumerate(checkpoints, start=1): dist = abs(ax - cx) + abs(ay - cy) if dist < best_dist or (dist == best_dist and idx < best): best_dist = dist best = idx print(best) if __name__ == '__main__': main()That works.
I'll now answer. ```python
import sys
def main(): input = sys.stdin.readline N, M = map(int, input().split())
students = [tuple(map(int, input().split())) for _ in range(N)] checkpoints = [tuple(map(int, input().split())) for _ in range(M)] for ax, ay in students: best_idx = 0 # will hold the answer (1‑based) best_dist = 10**18 # a very large number for idx, (cx, cy) in enumerate(checkpoints, start=1): dist = abs(ax - cx) + abs(ay - cy) # update if strictly better, or equal distance but smaller index if dist < best_dist or (dist == best_dist and idx < best_idx): best_dist = dist best_idx = idx print(best_idx)if name == "main": main()