Problem:


問題 ４

　平面上の n 個の点 P1, ..., Pn が与えられたとき，
距離が最小の２点を求めたい．

　入力ファイルの１行目には整数 n が書いてある．
２行目から n+1 行目のそれぞれには，
２つの正整数 x, y が１つの半角空白文字を区切りとして書いてある．
i+1 行目の x, y はそれぞれ Pi の x 座標，
Pi の y 座標である．
これら n 点の中から最も近い２点を選んだとき，
この２点間の距離の２乗を出力せよ．

8 かつ -10000≦x≦10000, -10000≦y≦10000 とし，
５つの入力ファイルのうち３つでは n≦100 である．
また，どの入力ファイルにおいても，全ての座標は異なるものとする．

-->

　ただし，
2≤n≤500000 かつ -10000≤x≤10000, -10000≤y≤10000 とし，
５つの入力ファイルのうち３つでは n≤100 である．
また，どの入力ファイルにおいても，全ての座標は異なるものとする．

出力ファイルにおいては，
出力の最後の行にも改行コードを入れること．

入出力例

入力例１

2
0 0
1 1

出力例１

2

入力例２

3
5 5
0 0
-3 -4

出力例２

25

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
2
0 0
1 1


Sample output:
2

Submission status: Wrong Answer

Solution code:
n = input()
print(n,'\n')
"""
i = 0
pointList = []
while(i<n):
 point0 = input()
 point0 = point0.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Wrong Answer

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 #pointStr = "0 0"
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Wrong Answer

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 #pointStr = "0 0"
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
#"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Wrong Answer

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 #pointStr = "0 0"
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')

Submission status: Wrong Answer

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
minX_diff = 2000000
minY_diff = 20000000
pointList2 = pointList
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList2):
  x_diff = abs(point1[0] - point2[0])
  y_diff = abs(point1[1] - point2[1])
  if((x_diff+y_diff)<(minX_diff+minY_diff)):
   minX_diff = x_diff
   minY_diff = y_diff
   dist = x_diff*x_diff + y_diff*y_diff
 pointList2.pop(0)
print(str(dist))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = sorted([tuple(map(int, input().split())) for i in range(N)])

d = 1000000000
for p1 in P:
    for p2 in P:
        if p1 == p2:
            continue
        if pow(p1[0] - p2[0], 2) >= d:
            break
        d = min(pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2), d)
print(d)

Submission status: Wrong Answer

Solution code:
import math
def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().split())))

    b = []
    for x in range(n):
        for y in range(n):
            if x == y:
                pass
            else:
                hoge = (a[x][0] - a[y][0]) ** 2 + (a[x][1] - a[y][1]) ** 2
                fuga = math.sqrt(hoge) ** 2
                b.append(int(fuga))

    b.sort()

    print(b[0])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def closest_part(points, n):
    # ?????¬???p324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m].x
    d = min(closest_part(points[:m], m), closest_part(points[m:], n-m))

    points.sort(key=lambda x:x.x)
    b = []
    for p in points:
        if (p.x - x)**2 >= d:
            continue
        for j in range(len(b)):
            dx = p.x - b[-j-1].x
            dy = p.y - b[-j-1].y
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.append(p)
    return d

pos = namedtuple('pos', ['x', 'y'])
def main(args):
    n = int(input())
    points = [pos(*list(map(int, input().split()))) for _ in range(n)]
    points.sort()               #  x????????§??????????????????

    result = closest_part(points, n)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
n=int(input())
d=[list(map(int,input().split()))for _ in[0]*n]
m=1e9
for i in range(n-1):
 for b in d[i+1:]:
  x,y=d[i]
  s,t=b
  l=(x-s)**2+(y-t)**2
  if m<l:m=l
print(m)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([complex(*map(int,input().split()))for _ in[0]*n],key=lambda x:x.real)
m=1e9
for i in range(1,n):
 z=a[i]
 for w in a[:i][::-1]:
  if z.real-w.real>m:break
  m=min(m,abs(w-z))
print(m*m)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([complex(*map(int,input().split()))for _ in[0]*n],key=lambda x:x.real)
m=1e9
for i in range(1,n):
 z=a[i]
 for w in a[:i][::-1]:
  if z.real-w.real>m:break
  m=min(m,abs(w-z))
print(int(m*m))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([complex(*map(int,input().split()))for _ in[0]*n],key=lambda x:x.real)
m=1e9
for i in range(1,n):
 z=a[i]
 for w in a[:i][::-1]:
  if z.real-w.real>m:break
  m=min(m,abs(w-z)**2)
print(m)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import math
n = int(input())
p = []
def dist(i, j):
    global p
    return (p[j][0] - p[i][0]) ** 2 + (p[j][1] - p[i][1]) ** 2
for d in sys.stdin:
    p.append(tuple(list(map(int, d.split()))))
p.sort()
mind = dist(0, 1)
minl = math.sqrt(mind)
for i in range(n):
    for j in range(i, n):
        if p[j][0] - p[i][0] > minl:
            break
        d = dist(i, j)
        if d < mind:
            mind = d
            minl = math.sqrt(mind)
print(mind)

Submission status: Wrong Answer

Solution code:
class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def norm(self, pnt):
        return (pnt.x - self.x)**2 + (pnt.y - self.y)**2

n = int(input())
points = []
for i in range(n):
    x, y = list(map(int, input().split(' ')))
    points.append(Point(x, y))

min_dist = float('inf')
for i in range(n-1):
    for j in range(i+1, n):
        dist = points[i].norm(points[j])
        if min_dist > dist:
            min_dist = dist

print(dist)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = []
for i in range(n):
    x, y = map(int, input().split())
    a.append((x, y))

b = []
for i in range(n-1):
    for j in range(i+1, n):
        p1 = a[i]; p2 = a[j]
        b.append(math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2))

print(int(min(b)**2))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = []
for i in range(n):
    x, y = map(int, input().split())
    a.append((x, y))

b = []
for i in range(n-1):
    for j in range(i+1, n):
        p1 = a[i]; p2 = a[j]
        b.append(math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2))

print(min(b)**2)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
from itertools import combinations, takewhile
from math import sqrt

def solve(a: list, sorted_axis: int = -1, d_ub = 10**12):
    length = len(a)
    if length <= 3:
        return min((x1-x2)**2+(y1-y2)**2 for (x1, y1), (x2, y2) in combinations(a, 2))

    x_set_len = len(set(x for x, _ in a))
    axis1 = 0 if x_set_len > length/2 else 1

    if sorted_axis != axis1:
        a.sort(key=itemgetter(axis1))
        if (a[-1][axis1] - a[0][axis1])**2 >= d_ub:
            return d_ub

    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta_left = solve(left, axis1, d_ub) if (left[-1][axis1]-left[0][axis1])**2 < d_ub else d_ub
    delta_right = solve(right, axis1, delta_left) if (right[-1][axis1]-right[0][axis1])**2 < d_ub else d_ub
    delta = delta_left if delta_left < delta_right else delta_right

    axis2 = not axis1
    median = a[mid_index][axis1]
    mid_a = sorted([p for _iter in (
        (takewhile(lambda p: median-sqrt(delta) < p[axis1], left[::-1])),
        (takewhile(lambda p: p[axis1] < median+sqrt(delta), right))
    ) for p in _iter], key=itemgetter(axis2))

    for i, (x1, y1) in enumerate(mid_a):
        ub = (x1 if axis1 else y1) + sqrt(delta)
        for x2, y2 in takewhile(lambda p: p[axis2] < ub, mid_a[i+1:]):
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    a = [tuple(map(int, l.split())) for l in sys.stdin.readlines()]
    print(solve(a))

Submission status: Wrong Answer

Solution code:
import math
n=input()
L=[map(int,raw_input().split()) for i in range(n)]
L.sort()
m=10e20
for i in range(n-1):
       m=min(m,pow(L[i][0]-L[i+1][0],2)+pow(L[i][1]-L[i+1][1],2))
print m

Submission status: Wrong Answer

Solution code:
n = input()
a = [map(int,raw_input().split()) for i in range(n)]
a.sort()
L = 10e20
for i in range(n-1):
       L = pow(a[i][0]-a[i-1][0],2)+pow(a[i][1]-a[i-1][1],2)
       for j in reversed(range(i)):
              if abs(a[j][0]-a[i+1][0])>=L:
                     break
              L = min(L, pow(a[j][0]-a[i+1][0],2)+pow(a[j][1]-a[i+1][1],2))
print L

Submission status: Wrong Answer

Solution code:
import math
n = input()
a = [map(int,raw_input().split()) for i in range(n)]
a.sort()
L = pow(a[1][0]-a[0][0],2)+pow(a[1][1]-a[0][1],2)
for i in range(1, n-1):
       t = math.sqrt(L)
       for j in reversed(range(i)):
              if a[i+1][0]-a[j][0]>=t:
                     break
              L = min(L, pow(a[j][0]-a[i+1][0],2)+pow(a[j][1]-a[i+1][1],2))
print L

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 #pointStr = "0 0"
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if((x_diff+y_diff)<(minX_diff+minY_diff)):
    minX_diff = x_diff
    minY_diff = y_diff
    dist = x_diff*x_diff + y_diff*y_diff
print(str(dist))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i<j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if((x_diff+y_diff)<(minX_diff+minY_diff)):
    minX_diff = x_diff
    minY_diff = y_diff
    dist = x_diff*x_diff + y_diff*y_diff
print(str(dist))

Submission status: Memory Limit Exceeded

Solution code:
n = input()
i = 0
pointList = []
while True:
 #pointStr = input()
 pointStr = "0 0"
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
points = [list(map(int,input().split())) for i in range(n)]
dist_list = []
for x, y in points:
    for x2, y2 in points:
        if x == x2 and y == y2:
            continue
        dist_list.append((x - x2)**2 + (y - y2)**2)
print(min(dist_list))

Submission status: Memory Limit Exceeded

Solution code:
n=int(input())
d=[list(map(int,input().split()))for _ in[0]*n]
l=[]
for i in range(n-1):
 for b in d[i+1:]:
  x,y=d[i]
  s,t=b
  l+=[(x-s)**2+(y-t)**2]
print(min(l))

Submission status: Memory Limit Exceeded

Solution code:
n=int(input())
d=[list(map(int,input().split()))for _ in[0]*n]
m=1e9
l=[]
for i in range(n-1):
 for b in d[i+1:]:
  x,y=d[i]
  s,t=b
  l+=[(x-s)**2+(y-t)**2]
print(min(l))

Submission status: Memory Limit Exceeded

Solution code:
n=int(input())
i=0
x=[]
y=[]
while i<n:
    l=[]
    l=input().split()
    x.append(int(l[0]))
    y.append(int(l[1]))
    i+=1

X=[]
Y=[]
for a in range(0,n):
    for b in range(0,n):
        if a==b:
            pass
        else:
            X.append((x[a]-x[b])*(x[a]-x[b]))
            Y.append((y[a]-y[b])*(y[a]-y[b]))

A=[]
for i in range(0,len(X)):
    A.append(X[i]+Y[i])

print(min(A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585

"""
import sys
from sys import stdin
from math import sqrt
input = stdin.readline


def closest_part(points, n):
    # ?????¬???p324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part(points[:m], m), closest_part(points[m:], n-m))

    points.sort(key=lambda x:x[1])
    b = []
    for i in range(n):
        if (points[i][0] - x)**2 >= d:
            continue
        for j in range(len(b)):
            dx = points[i][0] - b[-j-1][0]
            dy = points[i][1] - b[-j-1][1]
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.append(points[i])
    return d


def main(args):
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    points.sort()               #  x????????§??????????????????

    result = closest_part(points, n)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def closest_part(points, n):
    # ?????¬???p324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m].x
    d = min(closest_part(points[:m], m), closest_part(points[m:], n-m))

    points.sort(key=lambda p:p.y)
    b = []
    for p in points:
        if (p.x - x)**2 >= d:
            continue
        for j in range(len(b)):
            dx = p.x - b[-j-1].x
            dy = p.y - b[-j-1].y
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.append(p)
    return d

pos = namedtuple('pos', ['x', 'y'])
def main(args):
    n = int(input())
    points = [pos(*list(map(int, input().split()))) for _ in range(n)]
    points.sort()               #  x????????§??????????????????

    result = closest_part(points, n)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline


def closest_part(points, n):
    # ?????¬???p324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part(points[:m], m), closest_part(points[m:], n-m))

    points.sort(key=lambda p:p[1])
    b = []
    for p in points:
        if (p[0] - x)**2 >= d:
            continue
        for q in b[::-1]:
            # dx = p[0] - b[-j-1][0]
            # dy = p[1] - b[-j-1][1]
            dx = p[0] - q[0]
            dy = p[1] - q[1]
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.append(p)
    return d

def main(args):
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    points.sort()               #  x????????§??????????????????

    result = closest_part(points, n)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585

"""
import sys
from sys import stdin
input = stdin.readline


def closest_part(points, n):
    # ?????¬???p324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part(points[:m], m), closest_part(points[m:], n-m))

    points.sort(key=lambda p:p[1])
    b = []
    for p in points:
        if (p[0] - x)**2 >= d:
            continue
        for q in b:
            dx = p[0] - q[0]
            dy = p[1] - q[1]
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.insert(0, p)
    return d


def main(args):
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    points.sort()               #  x????????§??????????????????

    result = closest_part(points, n)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0585

"""
import sys
from sys import stdin
input = stdin.readline


def closest_part1(points, n):
    # ?????¬???p324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part1(points[:m], m), closest_part1(points[m:], n-m))

    points.sort(key=lambda x:x[1])
    b = []
    for i in range(n):
        if (points[i][0] - x)**2 >= d:
            continue
        for j in range(len(b)):
            dx = points[i][0] - b[-j-1][0]
            dy = points[i][1] - b[-j-1][1]
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.append(points[i])
    return d


def closest_part2(points, n):
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part2(points[:m], m), closest_part2(points[m:], n-m))
    points.sort(key=lambda p:p[1])
    b = []
    for p in points:
        if (p[0] - x)**2 >= d:
            continue
        for q in b:
            dx = p[0] - q[0]
            dy = p[1] - q[1]
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.insert(0, p)
    return d


def closest_part3(points, n):
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part3(points[:m], m), closest_part3(points[m:], n-m))
    points.sort(key=lambda p:p[1])
    b = []
    for p in points:
        if (p[0] - x)**2 >= d:
            continue
        for q in b[::-1]:
            dx = p[0] - q[0]
            dy = p[1] - q[1]
            if dy**2 >= d:
                break
            d = min(d, (dx**2 + dy**2))
        b.append(p)
    return d


def main(args):
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    points.sort()               #  x????????§??????????????????

    result = closest_part3(points, n)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
a = [tuple(map(int, input().split())) for _ in [0]*N]
ans = float("inf")

a.sort()
for (x1, y1), (x2, y2) in zip(a, a[1:]):
    dist = (x1-x2)**2 + (y1-y2)**2
    if ans > dist:
        ans = dist

a.sort(key=itemgetter(1))
for (x1, y1), (x2, y2) in zip(a, a[1:]):
    dist = (x1-x2)**2 + (y1-y2)**2
    if ans > dist:
        ans = dist

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
N = int(input())
a = sorted(tuple(map(int, l.split())) for l in sys.stdin.readlines())
ans = float("inf")

for (x1, y1), (x2, y2) in zip(a, a[1:]):
    dist = (x1-x2)**2 + (y1-y2)**2
    if ans > dist:
        ans = dist

a.sort(key=itemgetter(1))
for (x1, y1), (x2, y2) in zip(a, a[1:]):
    dist = (x1-x2)**2 + (y1-y2)**2
    if ans > dist:
        ans = dist

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from itertools import combinations, takewhile
from math import sqrt

def solve(a: list, sorted_axis: int = -1):
    length = len(a)
    if length <= 3:
        return min((x1-x2)**2+(y1-y2)**2 for (x1, y1), (x2, y2) in combinations(a, 2))

    x_set_len = len(set(x for x, _ in a))
    axis1 = 0 if x_set_len > length/2 else 1

    if sorted_axis != axis1:
        a.sort(key=itemgetter(axis1))

    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta = min(solve(left, axis1), solve(right, axis1))

    axis2 = not axis1
    median = a[mid_index][axis1]
    mid_a = sorted([p for _iter in (
        (takewhile(lambda p: median-sqrt(delta) < p[axis1], left[::-1])),
        (takewhile(lambda p: p[axis1] < median+sqrt(delta), right))
    ) for p in _iter], key=itemgetter(axis2))

    for i, (x1, y1) in enumerate(mid_a):
        ub = (x1 if axis1 else y1) + sqrt(delta)
        for x2, y2 in takewhile(lambda p: p[axis2] < ub, mid_a[i+1:]):
            delta = min(delta, (x1-x2)**2+(y1-y2)**2)

    return delta

if __name__ == "__main__":
    N = int(input())
    a = [tuple(map(int, l.split())) for l in sys.stdin.readlines()]
    print(solve(a))

Submission status: Accepted

Solution code:
n = int(input())
P, Q = [], []
for i in range(0, n):
	a, b = map(int, input().split())
	P.append([a, b])
	Q.append([b, a])
P.sort()
Q.sort()
dist = 20000**2+20000**2
for p in range(0, n-1):
	temp = (P[p][0]-P[p+1][0])**2+(P[p][1]-P[p+1][1])**2
	if temp<dist: dist = temp
for q in range(0, n-1):
	temp = (Q[q][0]-Q[q+1][0])**2+(Q[q][1]-Q[q+1][1])**2
	if temp<dist: dist = temp
print(dist)

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append([x, y])
    b.append([y, x])
a.sort()
b.sort()
L = (a[1][0] - a[0][0]) ** 2 + (a[1][1] - a[0][1]) ** 2
for i in range(n - 1):
    dis = (a[i+1][0] - a[i][0]) ** 2 + (a[i+1][1] - a[i][1]) ** 2
    if L > dis:
        L = dis
for i in range(n - 1):
    dis = (b[i+1][0] - b[i][0]) ** 2 + (b[i+1][1] - b[i][1]) ** 2
    if L > dis:
        L = dis
print(L)

Submission status: Accepted

Solution code:
# coding: utf-8

def closest_pair(P, n):
    if n <= 1:
        return float('inf')

    m = n // 2
    x = P[m][0]
    d = min(closest_pair(P[:m], m), closest_pair(P[m:], n-m))
    P.sort(key=lambda p: p[1])

    Q = []
    for p in P:
        if (p[0] - x)**2 >= d:
            continue

        for q in Q:
            dx = p[0] - q[0]
            dy = p[1] - q[1]

            if dy**2 >= d:
                break

            d = min(d, dx**2 + dy**2)

        Q.insert(0, p)

    return d


N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
P.sort()
print(closest_pair(P, N))

Submission status: Accepted

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

b = sorted(a, key = lambda x: (x[0], x[1]))
c = sorted(a, key = lambda x: (x[1], x[0]))

ans = 10**10
for i in range(n-1):
    temp = (b[i+1][0]-b[i][0])**2 + (b[i+1][1]-b[i][1])**2 
    if ans > temp:
        ans = temp
for i in range(n-1):
    temp = (c[i+1][0]-c[i][0])**2 + (c[i+1][1]-c[i][1])**2 
    if ans > temp:
        ans = temp
    
print(ans)

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(i<n):
 point0 = input().split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(i<n):
 point0 = input().split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
print(dist,'\n')
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(i<n):
 point0 = input()
 point0 = point0.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
print(dist,'\n')
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(i<n):
 point0 = input()
 point0 = point0.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
print(dist,'\n')

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(i<n):
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(i<=n):
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while(True):
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while True:
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Runtime Error

Solution code:
n = input()
i = 0
pointList = []
while True:
 pointStr = input()
 point0 = pointStr.split()
 #point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
print(dist,'\n')
#"""
"""
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!=j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if(x_diff+y_diff<minX_diff+minY_diff):
    dist = x_diff*x_diff + y_diff*y_diff
print(dist,'\n')
#"""

Submission status: Runtime Error

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 #pointStr = "0 0"
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
minX_diff = 2000000
minY_diff = 20000000
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList):
  if(i!<j):
   x_diff = abs(point1[0] - point2[0])
   y_diff = abs(point1[1] - point2[1])
   if((x_diff+y_diff)<(minX_diff+minY_diff)):
    minX_diff = x_diff
    minY_diff = y_diff
    dist = x_diff*x_diff + y_diff*y_diff
print(str(dist))

Submission status: Runtime Error

Solution code:
n = int(input())
i = 0
pointList = []
while True:
 pointStr = input()
 point0 = pointStr.split()
 point = [int(point0[0]),int(point0[1])]
 pointList.append(point)
 i+=1
 if(i==n):
  break
dist = 0
minX_diff = 2000000
minY_diff = 20000000
pointList2 = pointList
for i,point1 in enumerate(pointList):
 for j,point2 in enumerate(pointList2):
  x_diff = abs(point1[0] - point2[0])
  y_diff = abs(point1[1] - point2[1])
  if((x_diff+y_diff)<(minX_diff+minY_diff)):
   minX_diff = x_diff
   minY_diff = y_diff
   dist = x_diff*x_diff + y_diff*y_diff
 pointList2.remove(0)
print(str(dist))

Submission status: Runtime Error

Solution code:
N = int(input())
P = sorted([tuple(map(int, input().split())) for i in range(N)])
d = 1000000000

for i, p1 in enumerate(P):
    for p2 in P[i + 1:]:
        if pow(p1[0] - p2[0], 2) > d:
            break
        d = min(pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2), d)
print(d)

Submission status: Runtime Error

Solution code:
N = int(input())
P = sorted([tuple(map(int, input().split())) for i in range(N)])
d = 1000000000

for i in range(len(P)):
    for j in range(i + 1, len(P)):
        p1, p2 = P[i], P[j]
        if pow(p1[0] - p2[0], 2) > d:
            break
        d = min(pow(p1[0] - p2[0], 2) + pow(p1[1] - p2[1], 2), d)
print(d)