5.Shadow Fiend


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type

Shadow Fiend là một con quái vật đem lại nỗi khiếp sợ cho nhiều người. Ở một ngôi làng nọ, có N người dân sinh sống ở đây và được thể hiện trên mặt phẳng tọa độ Oxy với tọa độ lần lượt là (a_i, b_i) với 1 \le i \le N . Do rất sợ Shadow Fiend nên người dân ở đây đã xây dựng M hầm trú ẩn khác nhau với toạn độ (c_j, d_j) với 1 \le j \le M . Khi có tín hiệu cảnh báo nguy hiểm, mọi người sẽ tìm đến hầm trú ẩn gần nhất được tính theo công thức khoảng cách Mahattan. Công thức được hiểu như sau:

Cho 2 điểm P_1(x_1, y_1)P_2(x_2, y_2) thì khoảng cách Mahattan giữa 2 điểm được tính là : D = |x_1 - x_2| + |y1 - y2|. Nếu như có nhiều hầm trú ẩn có cùng khoảng cách nhỏ nhất thì chọn hầm có chỉ số bé nhất.

Hãy lập trình để cho mỗi người dân biết mình sẽ trú ẩn ở hầm nào nhé các bạn nhé.

Input:

  • Dòng duy nhất gồm 2 số nguyên N,M,( 1 \le N, M \le 50)
  • N dòng tiếp theo gồm 2 số là tọa độ của người thứ i ( -10^8 \le a_i, b_i \le 10^8)
  • M dòng tiếp theo gồm 2 là tọa độ của hầm thứ j ( -10^8 \le a_j, b_j \le 10^8)

Output:

  • Vỡi mỗi dòng thứ i ( 1 \le i \le N), In ra chỉ số của của hầm trú ẩn mà người dân thứ i sẽ ẩn nấp.

Example:

Input 1:

2 2

2 0

0 0

-1 0

1 0

Output 1:

2

1

Giải thích

Khoảng cách của người thứ nhất đến 2 hầm lần lượt là 3 và 1 -> người thứ nhất chọn hầm có chỉ số là 2 với khoảng cách là 1. Người thứ 2 khoảng cách lần lượt đến 2 hầm đều là 1 -> người 2 chọn hầm có chỉ số nhỏ nhất là 1.

Input 2:

3 4

10 10

-10 -10

3 3

1 2

2 3

3 5

3 5

Output 2:

3
1
2

Comments

There are no comments at the moment.