Problem:


Score : 200 points

Problem Statement

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.

Sample Input 1

2 2
2 0
0 0
-1 0
1 0

Sample Output 1

2
1

The Manhattan distance between the first student and each checkpoint is:

For checkpoint 1: |2-(-1)|+|0-0|=3

For checkpoint 2: |2-1|+|0-0|=1

The nearest checkpoint is checkpoint 2. Thus, the first line in the output should contain 2.

The Manhattan distance between the second student and each checkpoint is:

For checkpoint 1: |0-(-1)|+|0-0|=1

For checkpoint 2: |0-1|+|0-0|=1

When there are multiple nearest checkpoints, the student will go to the checkpoint with the smallest index. Thus, the second line in the output should contain 1.

Sample Input 2

3 4
10 10
-10 -10
3 3
1 2
2 3
3 5
3 5

Sample Output 2

3
1
2

There can be multiple checkpoints at the same coordinates.

Sample Input 3

5 5
-100000000 -100000000
-100000000 100000000
100000000 -100000000
100000000 100000000
0 0
0 0
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000

Sample Output 3

5
4
3
2
1



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


Sample output:
2
1

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
cd=[list(map(int,input().split())) for i in range(m)]

for a,b in ab:
    ans=-1
    kyori=float('inf')
    i=1
    for c,d in cd:
        if kyori>abs(a-c)+abs(b-d):
            ans=i
            kyori=abs(a-c)+abs(b-d)
        i+=1
    print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().rstrip().split(" "))
stu = [[] for i in range(N)]
che = [[] for i in range(M)]
for i in range(N):
    stu[i] = list(map(int,input().rstrip().split(" ")))
for i in range(M):
    che[i] = list(map(int,input().rstrip().split(" ")))
for i in range(N):
    ansnum = 0
    ansdis = 10 ** 9
    for i2 in range(M):
        if abs(che[i2][0] - stu[i][0]) + abs(che[i2][1] - stu[i][1]) < ansdis:
            ansnum= i2 + 1
            ansdis = abs(che[i2][0] - stu[i][0]) + abs(che[i2][1] - stu[i][1])
    print(ansnum)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
AB = []
for i in range(n):
    a,b = readInts()
    AB.append((a,b))
CD = []
for i in range(m):
    c,d = readInts()
    CD.append((c,d))
for i in range(n):
    a,b = AB[i]
    MIN = float('inf')
    idx = -1
    for j in range(m):
        c,d = CD[j]
        if abs(a - c) + abs(b - d) < MIN:
            MIN = abs(a-c) + abs(b-d)
            idx = j+1
    print(idx)

Submission status: Accepted

Solution code:
def solve():
  N, M = map(int, input().split())
  ans = [0]*N
  A = [0]*N
  B = [0]*N
  for i in range(N):
    A[i],B[i] = map(int, input().split())
  X = [0]*M
  Y = [0]*M
  for i in range(M):
    X[i],Y[i] = map(int, input().split())
  for i in range(N):
    ind = -1
    d_min = float('inf')
    for j in range(M):
      d = abs(A[i]-X[j])+abs(B[i]-Y[j])
      if d<d_min:
        d_min = d
        ind = j+1
    ans[i] = ind
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, M = inm()
st = []
for i in range(N):
    a, b = inm()
    st.append((a, b))
cp = []
for i in range(M):
    c, d = inm()
    cp.append((c, d))


def solve():
    for i in range(N):
        a, b = st[i]
        mindis = 10 ** 12
        mcp = None
        for j in range(M):
            c, d = cp[j]
            dis = abs(a - c) + abs(b - d)
            if mindis > dis:
                mindis = dis
                mcp = j + 1
        print(mcp)


solve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
AB = []
CD = []
for i in range(n):
    a,b = map(int,input().split())
    AB.append([a,b])
for i in range(m):
    c,d = map(int,input().split())
    CD.append([c,d])

for st in range(n):
    ans = float("inf")
    for po in range(m):
        dist = abs(AB[st][0]-CD[po][0])+abs(AB[st][1]-CD[po][1])
        if ans > dist:
            ans = dist
            memo = po + 1
    print(memo)

Submission status: Accepted

Solution code:
def dist(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])
N,M = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
Y = [list(map(int,input().split())) for _ in range(M)]
for i in range(N):
    x,y = X[i]
    ind = M+1
    dmin = 10**9
    for j in range(M):
        c,d = Y[j]
        d = dist((x,y),(c,d))
        if d<dmin:
            ind = j+1
            dmin = d
    print(ind)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]
CD = [tuple(map(int,input().split())) for i in range(M)]
for a,b in AB:
    best_i = -1
    best_d = 10**9
    for i,(c,d) in enumerate(CD):
        dist = abs(a-c) + abs(b-d)
        if dist < best_d:
            best_d = dist
            best_i = i
    print(best_i + 1)

Submission status: Accepted

Solution code:
MM = input().split()
N = int(MM[0])
M = int(MM[1])
list1 = []
list2 = []
for i in range(N):
  LL = input().split()
  list1.append(LL)

for i in range(M):
  MM = input().split()
  list2.append(MM)

for i in list1:
  mini = 40**8
  ans = 0
  for j in range(len(list2)):
    x = int(i[0]) - int(list2[j][0])
    y = int(i[1]) - int(list2[j][1])
    xx = abs(x) + abs(y)
    if xx < mini:
      mini = xx
      ans = j+1
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()
exec("try:sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w')\nexcept:pass")

n, m = map(int, input().split())
student, point = [], []
for i in range(n):
    student.append(list(map(int, input().split())))
for i in range(m):
    point.append(list(map(int, input().split())))
dist = []
for i in range(n):
    temp = []
    for j in range(m):
        temp.append([j, abs(student[i][0] - point[j][0]) +
                     abs(student[i][1] - point[j][1])])
    dist.append(temp)
# for dis in dist:
#     print(dis)
tot = []
for dis in dist:
    ans = []
    minn = min(dis, key=lambda i: i[1])
    for i in dis:
        if i[1] == minn[1]:
            ans.append(i[0])
    ans.sort()
    print(ans[0] + 1)
# print(tot)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
P = [list(map(int, input().split())) for _ in range(N)]
Q = [list(map(int, input().split())) for _ in range(M)]

for i in range(N):
    d = 10 ** 9
    res = 0
    for j in range(M):
        _d = abs(P[i][0] - Q[j][0]) + abs(P[i][1] - Q[j][1])
        if _d < d:
            d = _d
            res = j + 1
    print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
st=[]
ch=[]
def mht(ax,ay,bx,by):
  return abs(ax-bx)+abs(ay-by)

for i in range(n):
  st.append(list(map(int,input().split())))
for i in range(m):
  ch.append(list(map(int,input().split())))
  
for i in st:
  ax=i[0]
  ay=i[1]
  mn=1000000000
  for (j,k) in zip(ch,range(len(ch))):
    bx=j[0]
    by=j[1]
    mh=mht(ax,ay,bx,by)
    if mh<mn:
      mn=mh
      nm=k
  print(nm+1)

Submission status: Accepted

Solution code:
def f(X,Y):
    return abs(X[0]-Y[0])+abs(X[1]-Y[1])

inf=float("inf")
N,M=map(int,input().split())

P=[]
for _ in range(N):
    a,b=map(int,input().split())
    P.append((a,b))

Q=[("*","*")]
for _ in range(M):
    c,d=map(int,input().split())
    Q.append((c,d))

S=[]
for X in P:
    D=inf
    J=0
    for k in range(1,M+1):
        if D>f(X,Q[k]):
            D=f(X,Q[k])
            J=k

    S.append(J)

print("\n".join(map(str,S)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
C = [list(map(int, input().split())) for _ in range(M)]

for n in range(N):
    d_lst = []
    for m in range(M):
        dis = abs(A[n][0] - C[m][0]) + abs(A[n][1] - C[m][1])
        d_lst.append(dis)
    print(d_lst.index(min(d_lst)) + 1)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,M = I()
a = [l() for _ in range(N)]
b = [l() for _ in range(M)]
for i in range(N):
    num1 = INF
    num2 = 0
    for j in range(M):
        if abs(b[j][0]-a[i][0])+abs(b[j][1]-a[i][1]) < num1:
            num1 = abs(b[j][0]-a[i][0])+abs(b[j][1]-a[i][1])
            num2 = j+1
    print(num2)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(m)]
ans = [0]*n
for i in range(n):
    count = 10**9
    for j in range(m):
        ch = abs(ab[i][0] - cd[j][0]) + abs(ab[i][1] - cd[j][1])
        if ch < count:
            ans[i] = j+1
            count = ch
    print(ans[i])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(m)]
ans = [0]*n
for i in range(n):
    count = 10**9
    for j in range(m):
        ch = abs(ab[i][0] - cd[j][0]) + abs(ab[i][1] - cd[j][1])
        #print("i =",i,"j=",j,"ch =",ch,count)
        if ch < count:
            ans[i] = j+1
            count = ch
    print(ans[i])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = []
b = []
c = []
d = []
ans = []

for n in range(N):
  A, B = map(int, input().split())
  a.append(A)
  b.append(B)

for m in range(M):
  C, D = map(int, input().split())
  c.append(C)
  d.append(D)

for i in range(N):
  l = []
  for j in range(M):
    l.append(abs(a[i] - c[j]) + abs(b[i] - d[j]))
  print(l.index(min(l))+1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))

cd = []
for _ in range(m):
    cd.append(list(map(int, input().split())))

tmp = []
for i in range(n):
    ans = 10**9 +7
    ta = 0
    for j in range(m):
        x  = abs(ab[i][0] - cd[j][0])
        y =  abs(ab[i][1] - cd[j][1])
        if ans > x+y:
            ans = x+y
            ta = j+1
    print(ta)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
s = [tuple(map(int,input().split())) for _ in range(n)]
c = [tuple(map(int,input().split())) for _ in range(m)]
for i in range(n):
  mini = 0
  m_i = 0
  for j in range(m):
    dis = abs(s[i][0]-c[j][0])+abs(s[i][1]-c[j][1])
    if j==0:
      mini, m_i = dis, j+1
      continue
    elif mini > dis:
      mini, m_i = dis, j+1
  print(m_i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n, m = [int(x) for x in input().split()]
    s = []
    for _ in range(n):
        s.append([int(x) for x in input().split()])
    c = []
    for _ in range(m):
        c.append([int(x) for x in input().split()])
    for x, y in  s:
        ans = 0
        d = float('inf')
        for i, (a, b) in enumerate(c):
            if abs(x-a) + abs(y-b) < d:
                ans = i
                d = abs(x-a) + abs(y-b)
        print(ans + 1)
        

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""


"""

Submission status: Accepted

Solution code:
import math

def calc_dist(pta, ptb):
    return abs(pta[0] - ptb[0]) + abs(pta[1] - ptb[1])

n, m = map(int, input().split())
stdts = [tuple(map(int, input().split())) for _ in range(n)]
cpts = [tuple(map(int, input().split())) for _ in range(m)]

for stdt in stdts:
    dist_min = math.inf
    for i in range(m):
        dist = calc_dist(stdt, cpts[i])
        if dist < dist_min:
            dist_min = dist
            ans = i + 1
    print(ans)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def f(x1, x2, y1, y2):
    return abs(x1 - x2) + abs(y1 - y2)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    AB = [il() for _ in range(N)]
    CD = [il() for _ in range(M)]
    for a, b in AB:
        ret = MAX
        dist = MAX
        for m in range(M):
            c, d = CD[m]
            d = f(a, c, b, d)
            if d == dist:
                ret = min(m + 1, ret)
            elif d < dist:
                dist = d
                ret = m + 1
        print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = []
B = []
C = []
D = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(m):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

for i in range(n):
    dis = []
    for j in range(m):
        dis.append(abs(A[i] - C[j]) + abs(B[i] - D[j]))
    mi = min(dis)
    for j in range(m):
        if dis[j] == mi:
            print(j + 1)
            break

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
seito=[]
for i in range(n):
    a,b=map(int,input().split())
    seito.append([a,b])
point=[]
for i in range(m):
    c,d=map(int,input().split())
    point.append([c,d])

ans=[float("inf")]*n
for i in range(n):
    a,b=seito[i]
    min_kyori=float("inf")
    for j in range(m):
        c,d=point[j]
        kyori=abs(a-c)+abs(b-d)
        if kyori<min_kyori:
            min_kyori=kyori
            ans[i]=j+1

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
student = []
for i in range(n):
  student.append(tuple(map(int, input().split())))
point = []
for i in range(m):
  point.append(tuple(map(int, input().split())))
for i in range(n):
  dis = 10 ** 20
  idx = 0
  for j in range(m):
    temp = abs(student[i][0] - point[j][0]) + abs(student[i][1] - point[j][1])
    if temp < dis:
      dis = temp
      idx = j + 1
  print(idx)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, M = mi()
    a, b = i2(N)
    c, d = i2(M)

    for i in range(N):
        dist = 10**10
        for j in range(M):
            if dist > abs(a[i]-c[j])+abs(b[i]-d[j]):
                cp = j+1
                dist = abs(a[i]-c[j])+abs(b[i]-d[j])
        print(cp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(N)]
y = [list(map(int, input().split())) for _ in range(M)]
for a,b in x:
    z = [abs(a-c) + abs(b-d) for c,d in y]
    print(z.index(min(z))+1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# ab = [int(x) for _ in range(N) for x in input().split()]
ab = [list(map(int, input().split())) for _ in range(N)]
cd = [list(map(int, input().split())) for _ in range(M)]

for st in range(len(ab)):
    dis = [abs(ab[st][0] - cd[cp][0]) + abs(ab[st][1] - cd[cp][1])  for cp in range(len(cd))]
    print(dis.index(min(dis))+1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

abes = [list(map(int, input().split())) for _ in range(n)]
cdes = [list(map(int, input().split())) for _ in range(m)]

for a, b in abes:
    mi = sorted(cdes, key=lambda x : abs(x[0]-a)+abs(x[1]-b))
    print(cdes.index(mi[0])+1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
nl = []
ml = []
for _ in range(n):
    nl.append(list(map(int,input().split())))
for _ in range(m):
    ml.append(list(map(int,input().split())))

for i in range(n):
    tmp=0
    ans=0
    for j in range(m):
        if ans:
            if tmp > abs(nl[i][0] - ml[j][0]) + abs(nl[i][1] - ml[j][1]):
                tmp = abs(nl[i][0] - ml[j][0]) + abs(nl[i][1] - ml[j][1])
                ans=j+1
        else:
            tmp = abs(nl[i][0] - ml[j][0]) + abs(nl[i][1] - ml[j][1])
            ans=j+1
    print(ans)

Submission status: Accepted

Solution code:
n, m= map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(m)]
ans = [0] * n
for i,ablist in enumerate(ab):
    mindist = 4 * (10**8)+1
    for j,cdlist in enumerate(cd):
        dist = abs(ablist[0]-cdlist[0])+abs(ablist[1]-cdlist[1])
        if dist < mindist:
            mindist = dist
            ans[i] = j+1
for i in range(n):
	print(ans[i])

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]

ab_list=[]
for i in range(n):
    a,b=[int(i) for i in input().split()]
    ab_list.append([a,b])
    
cd_list=[]
for i in range(m):
    c,d=[int(i) for i in input().split()]
    cd_list.append([c,d])
    
    
for i in range(n):
    len_list=[]
    for j in range(m):
        len=abs(ab_list[i][0]-cd_list[j][0])+abs(ab_list[i][1]-cd_list[j][1])
        len_list.append(len)
    print(len_list.index(min(len_list))+1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = []
for i in range(n):
  s.append(tuple(map(int,input().split())))
p = []
for i in range(m):
  p.append(tuple(map(int,input().split())))

for a,b in s:
  mnl = float('inf')
  for i in range(m):
    c,d = p[i]
    l = abs(a-c)+abs(b-d)
    if l < mnl:
      mnp = i+1
      mnl = l
  print(mnp)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
S = [list(map(int,input().split())) for _ in range(N)]
C = [list(map(int,input().split())) for _ in range(M)]
for a, b in S:
    distance = 1001001001
    ans = 0
    for i in range(len(C)):
        c, d = C[i][0], C[i][1]
        if abs(a - c) + abs(b - d) < distance:
            distance = abs(a - c) + abs(b - d)
            ans = i + 1
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
N = [list(map(int, input().split())) for _ in range(n)]
M = [list(map(int, input().split())) for _ in range(m)]


for i in range(n):
    ans = 0
    d = 9999999999999999999999
    for j in range(m):
        tmp = abs(N[i][0]-M[j][0]) + abs(N[i][1]-M[j][1])
        if tmp < d:
            d = tmp
            ans = j
    print(ans+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
stp = []
chp = []
for i in range(n):
    stp.append(list(map(int,input().split())))
for i in range(m):
    chp.append(list(map(int,input().split())))
for i in range(n):
    mdis =[]
    for j in range(m):
        mdis.append(abs(stp[i][0]-chp[j][0])+abs(stp[i][1]-chp[j][1]))
    print(mdis.index(min(mdis))+1)