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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

N, M = list(map(int, input().split()))
students = []
checkpoints = []

for i in range(N):
    a, b = list(map(int, input().split()))
    students.append([a, b])

for i in range(N):
    a, b = list(map(int, input().split()))
    checkpoints.append([a, b])

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import pprint
from queue import Queue


N, M = list(map(int, input().split()))
students = []
checkpoints = []

for i in range(N):
    a, b = list(map(int, input().split()))
    students.append([a, b])

for i in range(N):
    a, b = list(map(int, input().split()))
    checkpoints.append([a, b])

for student in students:
    min_dist = float('inf')
    min_i = None
    for i, checkpoint in enumerate(checkpoints):
        manhattan_dist = abs(checkpoint[0] - student[0]) + abs(checkpoint[1] - student[1])
        if manhattan_dist < min_dist:
            min_dist = manhattan_dist
            min_i = i
    print(min_i + 1)

Submission status: Runtime Error

Solution code:
mport numpy as np
N,M = map(int,raw_input().split())
a = []
c = []
for i in range(N):
    a.append(map(int,raw_input().split()))
#print a
for j in range(M):
    c.append(map(int,raw_input().split()))
a = np.array(a)
c = np.array(c)
#print a.shape
#print c.shape
min = 100
index = np.zeros(N)
for i in range(N):
    for j in range(M):
        if min > np.abs(a[i][0]-c[j][0])+np.abs(a[i][1]-c[j][1]):
            min = np.abs(a[i][0]-c[j][0])+np.abs(a[i][1]-c[j][1])
            index[i] = j
        elif min == np.abs(a[i][0]-c[j][0])+np.abs(a[i][1]-c[j][1]):
            if j < index[i]:
                index[i] = j
index = index.astype(np.int32)
for i in range(N):
    print index[i]+1

Submission status: Runtime Error

Solution code:
mport numpy as np
N,M = map(int,raw_input().split())
a = []
c = []
for i in range(N):
    a.append(map(int,raw_input().split()))
#print a
for j in range(M):
    c.append(map(int,raw_input().split()))
a = np.array(a)
c = np.array(c)
#print a.shape
#print c.shape
min = 100
index = np.zeros(N)
for i in range(N):
    for j in range(M):
        if min > np.abs(a[i][0]-c[j][0])+np.abs(a[i][1]-c[j][1]):
            min = np.abs(a[i][0]-c[j][0])+np.abs(a[i][1]-c[j][1])
            index[i] = j
        if min == np.abs(a[i][0]-c[j][0])+np.abs(a[i][1]-c[j][1]):
            if j < index[i]:
                index[i] = j
index = index.astype(np.int32)
for i in range(N):
    print index[i]+1

Submission status: Runtime Error

Solution code:
#include <iostream>
#Include <vector>
#include <algorithm>

using namespace std;

struct Point {
  int x, y;
  Point(int x, int y):x(x), y(y) { }
};

int main() {
  int N, M; cin >> N >> M;
  vector<Point> a(N);
  vector<Point> b(M);

  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    a[i] = Point(x, y);
  }

  for (int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    b[i] = Point(x, y);
  }

  for (int i = 0; i < N; i++) {
    Point &p = a[i];
    int idx = 0;
    int minval = 1e9+10;
    for (int j = 1; j < M; j++) {
      int val = abs(p.y - b[i],y) + abs(p.x - b[i].x);
      if (val < minval) {
        idx = j;
        minval = val;
      }
    }
    cout << idx << endl;
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
import math

n, m = map(int, input().split())

# student input
student = []
for i in range(n):
    a, b = map(int, input().split())
    student.append([a, b])

# check point input
check = []
for j in range(n):
    c, d = map(int, input().split())
    check.append([c, d])

# calc
for s in student:
    distance = 10e9
    near = 0
    for index, k in enumerate(check):
        v = math.fabs(s[0] - k[0]) + math.fabs(s[1] - k[1])
        if v < distance:
            distance = v
            near = index + 1
    print(near)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())

a, b = [map(int, raw_input().split()) for _ in xrange(N)]
c, d = [map(int, raw_input().split()) for _ in xrange(M)]

for i in xrange(N):
    for j in xrange(M):

        d = abs(a[i]-c[j]) + abs(b[i]-d[j])

        if j == 0:
            t = d
            ans = 1

        elif t > d:
            t = d
            ans = j+1

    print ans

Submission status: Runtime Error

Solution code:
# B-Checkpoints
# 問題URL:http://abc057.contest.atcoder.jp/tasks/abc057_b

N, M = map(int, input().split()) #まずNとMを取得
ABs = [] # 学生のいる座標
CDs = [] #　チェックポイントの座標

# 2行目よりN行分学生の座標を取得してABsに格納
for i in range(N):
    ABs.append([int(x) for x in input().split()])

# 2+N行目よりM行分チェックポイントの座標を取得してCDsに格納
for i in range(N):
    CDs.append([int(x) for x in input().split()])

for a,b in ABs:
    #ABsの中身をa,b、CDsの中身をc,dとして取り出し各チェックポイントごとの距離を測定
    distance = [abs(a-c) + abs(b-d) for c,d in CDs]
    
    #　距離が同じ場合は最も番号が早いものを出力する。=(min()はもともとそのようにできている。早いもの優先）
    #+1はリストは0番目から、チェックポイントは1番目から始まるため
    print(distance.index(min(distance)) + 1)

Submission status: Runtime Error

Solution code:
# B-Checkpoints
# 問題URL:http://abc057.contest.atcoder.jp/tasks/abc057_b

N, M = map(int, input().split()) #まずNとMを取得
ABs = [] # 学生のいる座標
CDs = [] #　チェックポイントの座標

# 2行目よりN行分学生の座標を取得してABsに格納
for i in range(N):
    ABs.append([int(x) for x in input().split()])

# 2+N行目よりM行分チェックポイントの座標を取得してCDsに格納
for i in range(N):
    CDs.append([int(x) for x in input().split()])

for a,b in ABs:
    #ABsの中身をa,b、CDsの中身をc,dとして取り出し各チェックポイントごとの距離を測定
    distance = [abs(a-c) + abs(b-d) for c,d in CDs]
    print(distance)
    
    #　距離が同じ場合は最も番号が早いものを出力する。=(min()はもともとそのようにできている。早いもの優先）
    #+1はリストは0番目から、チェックポイントは1番目から始まるため
    print(distance.index(min(distance)) + 1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
pos = []
che = []
for i in range(n):
    a,b=map(int,input().split())
    pos.append([a,b])
for i in range(m):
    a,b=map(int,input().split())
    che.append([a,b])

for i in range(n):
    dis = []
    for j in range(m):
        dis.append(abs(pos[i][0]-che[i][0])+abs(pos[i][1]-che[i][1]))
    print(dis.index(min(dis))+1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
print(n,m)
pos = []
che = []
for i in range(n):
    a,b=map(int,input().split())
    pos.append([a,b])
for i in range(m):
    a,b=map(int,input().split())
    che.append([a,b])

for i in range(n):
    dis = []
    for j in range(m):
        dis.append(abs(pos[i][0]-che[i][0])+abs(pos[i][1]-che[i][1]))
    print(dis.index(min(dis))+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]

student = list()
point = list()

for i in range(n):
    student.append([int(a) for a in input().split()])

for j in range(m):
    point.append([int(b) for b in input().split()])


mat = [[abs(student[i][0]-point[j][0]) + abs(student[i][1]-point[j][1]) for i in range(n)] for j in range(m)]

for i in range(n):
    print(mat[i].index(min(mat[i]))+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]

student = list()
point = list()

for i in range(n):
    student.append([int(a) for a in input().split()])

for j in range(m):
    point.append([int(b) for b in input().split()])


mat = [[abs(student[i][0]-point[j][0]) + abs(student[i][1]-point[j][1]) for j in range(m)] for i in range(m)]

for i in range(n):
    print(mat[i].index(min(mat[i]))+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]

student = list()
point = list()

for i in range(n):
    student.append([int(i) for i in input().split()])

for j in range(m):
    point.append([int(j) for j in input().split()])


mat = [[abs(student[i][0]-point[j][0]) + abs(student[i][1]-point[j][1]) for j in range(m)] for i in range(m)]

for i in range(n):
    print(mat[i].index(min(mat[i]))+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]

student = list()
point = list()

for i in range(n):
    student.append([int(i) for i in input().split()])

for j in range(m):
    point.append([int(i) for i in input().split()])


mat = [[abs(student[i][0]-point[j][0]) + abs(student[i][1]-point[j][1]) for j in range(m)] for i in range(m)]

for i in range(n):
    print(mat[i].index(min(mat[i]))+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]

student = list()
point = list()

for i in range(n):
    student.append([int(i) for i in input().split()])

for j in range(m):
    point.append([int(i) for i in input().split()])


mat = [[0 for j in range(m)] for i in range(m)]

for j in range(m):
    for i in range(n):
        mat[i][j] = abs(student[i][0]-point[j][0]) + abs(student[i][1]-point[j][1])

for i in range(n):
    print(mat[i].index(min(mat[i]))+1)

Submission status: Runtime Error

Solution code:
n,m=map(int,raw_input().split())
st=[]
ch=[]
l=[]
for i in range(n):
    g=map(int,raw_input().split())
    st.append(g)
for y in range(n):
    r=map(int,raw_input().split())
    ch.append(r)





def dis(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])

for stu in st:
    ctr=0
    gh=10**9+7
    new={}
    for che in ch:
        # print stu,che,dis(stu,che)
        if dis(stu,che)<gh:
            gh=dis(stu,che)
            ctr+=1
            if gh not in new:
                new[gh]=[ctr]
            else:
                new[gh].append(ctr)


        else:
            ctr+=1
    # print new
    po=new.keys()
    # print po
    po.sort()
    poi=new[po[0]]
    # print poi
    poi.sort()
    l.append(poi[0])
for numb in l:
    print numb

Submission status: Runtime Error

Solution code:
def get_min_distance_index(spos, check_pos):
    manhattan_distance = lambda x1, y1, x2, y2:abs(x1 - x2) + abs(y1 - y2)
    minimum = -1
    min_index = 0 

    for index, chpos in enumerate(check_pos):
        manhattan = manhattan_distance(spos[0], spos[1], chpos[0], chpos[1])
        if minimum < 0 or manhattan < minimum:
            minimum = manhattan
            min_index = index + 1

    return min_index


N, M = map(int, input().split())
student_pos = [[int(i) for i in input().split()]for _ in range(N)]
check_pos = [[int(i) for i in input().split()]for _ in range(N)]

for spos in student_pos:
    print(get_min_distance_index(spos, check_pos))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


def solve(s_pp, p_pp):
    p_nums = []
    for x, y in s_pp:
        distance = []
        for xx, yy in p_pp:
            n = abs(x - xx) + abs(y - yy)
            distance.append(n)
        min_distance_idx = distance.index(min(distance))
        p_nums.append(min_distance_idx + 1)
    return p_nums


def main():
    students, points = [int(e) for e in input().split()]
    students_ps = []
    points_ps = []

    for _ in range(students):
        x, y = [int(e) for e in input().split()]
        students_ps.append([x, y])
    for _ in range(points):
        x, y = [int(e) for e in input().split()]
        points_ps.append([x, y])
    
    for answer in solve(students_ps, points_ps):
        print(answer)


m

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
list_coStu = []
list_coChe = []
for i in range(N):
    list_coStu.append(list(map(int, input().split())))
for i in range(N):
    list_coChe.append(list(map(int, input().split())))

#calc distance

for iS in range(len(list_coStu)):
    coStu = np.array(list_coStu[iS])
    min_iC = 0
    d = 4 * 10**8 + 1
    for iC in range(len(list_coChe)):
        coChe = np.array(list_coChe[iC])
        dif = coChe - coStu
        dist = np.sum(np.abs(dif))
        if dist < d:
            min_iC = iC
            d = dist
    print(min_iC + 1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
student_pos = [[int(i) for i in input().split()]for _ in range(N)]
check_pos = [[int(i) for i in input().split()]for _ in range(N)]

manhattan_distance = lambda x1, y1, x2, y2:abs(x1 - x2) + abs(y1 - y2)

for spos in student_pos:
   distances =  [manhattan_distance(spos[0], spos[1], chpos[0],chpos[1]) for chpos in check_pos]
   print(distances.index(min(distances)) + 1)

Submission status: Runtime Error

Solution code:
N, M = raw_input().split()
ss = []
for i in range(N):
    ss.append(map(int, raw_input().split()))
ds = []
for i in range(M):
    ds.append(map(int, raw_input().split()))
res = []
for i in range(int(N)):
    max = 10000000000
    rank = 0
    for j in range(int(M)):
        dis = abs(s[0]-d[0]) + abs(s[1]-d[1])

#         dis = man_dis(ss[i],ds[j])
        if max > dis:
            rank = j+1
            max = dis
    print(rank)

Submission status: Runtime Error

Solution code:
N, M = raw_input().split()
ss = []
for i in range(N):
    ss.append(map(int, raw_input().split()))
ds = []
for i in range(M):
    ds.append(map(int, raw_input().split()))

def man_dis(s,d):
    dis = abs(s[0]-d[0]) + abs(s[1]-d[1])
    return dis

res = []
for i in range(int(N)):
    max = 10000000000
    rank = 0
    for j in range(int(M)):
        dis = man_dis(ss[i],ds[j])
        if max > dis:
            rank = j+1
            max = dis
    print(rank)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
list_coStu = []
list_coChe = []
for i in range(N):
    list_coStu.append(list(map(int, input().split())))
for i in range(N):
    list_coChe.append(list(map(int, input().split())))

#calc distance

for iS in range(len(list_coStu)):
    coStu = np.array(list_coStu[iS])
    min_iC = 0
    d = 2 * 10**8 + 1
    for iC in range(len(list_coChe)):
        coChe = np.array(list_coChe[iC])
        dif = coChe - coStu
        dist = np.sum(np.abs(dif))
        if dist < d:
            min_iC = iC
            d = dist
    print(min_iC + 1)

Submission status: Runtime Error

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

a = [[0, 0] for i in range(n)]

c = [[0, 0] for i in range(m)]

for i in range(n):
    a[i][0], a[i][1] = map(int, input().split())

for i in range(n):
    c[i][0], c[i][1] = map(int, input().split())

index = 0

for i in range(n):
    for j in range(m):
        if j == 0 :
            k = abs(a[i][0] - c[j][0]) + abs(a[i][1] - c[j][1]) +1

        di = abs(a[i][0] - c[j][0]) + abs(a[i][1] - c[j][1])
        if di < k:
            index = j + 1
            k = di
    print(index)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


def solve(s_pp, p_pp):
    p_nums = []
    for x, y in s_pp:
        distance = []
        for xx, yy in p_pp:
            n = abs(x, xx) + abs(y, yy)
            distance.append(n)
        p_nums.append(min(distance))
    return p_nums


def main():
    students, points = [int(e) for e in input().split()]
    students_ps = []
    points_ps = []

    for _ in range(students):
        x, y = [int(e) for e in input().split()]
        students_ps.append([x, y])
    for _ in range(points):
        x, y = [int(e) for e in input().split()]
        points_ps.append([x, y])
    
    for answer in solve(students_ps, points_ps):
        print(answer)


main()

Submission status: Runtime Error

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

a = [[0, 0] for i in range(n)]

c = [[0, 0] for i in range(m)]

for i in range(n):
    a[i][0], a[i][1] = map(int, input().split())

for i in range(n):
    c[i][0], c[i][1] = map(int, input().split())

index = 0

for i in range(n):
    k = 1<<20
    for j in range(m):
        di = abs(a[i][0] - c[j][0]) + abs(a[i][1] - c[j][1])
        if di < k:
            index = j + 1
            k = di
    print(index)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))

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

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

for ab_list in ab:
    min_distance = 200000000
    checkpoint = 0
    for cd_list in cd:
        checkpoint += 1
        distance = abs(ab_list[0] - cd_list[0]) + abs(ab_list[1] - cd_list[1])
        if distance < min_distance:
            min_distance = distance
            ans = checkpoint
    print(ans)