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

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):
    # ?????¬???lp324???
    if n <= 1:
        return float('inf')
    m = n // 2
    x = points[m][0]
    d = min(closest_part(points, m), closest_part(points[m:], n-m))

    points.sort(key=lambda x:x[1])
    b = []
    for i in range(n):
        if abs(points[i][0] - x) >= 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 >= 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: Runtime Error

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 abs(points[i][0] - x) >= 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 >= 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: Runtime Error

Solution code:
def get_n():
    return int(input())
def get_ns():
    return [int(a) for a in input().split()]
import math
def main():
    n = get_n()
    ns = [get_ns() for _ in range(n)]
    # ns = sorted(ns,key=lambda a:a[0])

    mind = 99999999
    res=9999999
    for i,a in enumerate(ns):
        x1,y1 = a
        for x2,y2 in ns[:i]:
            xd =abs(x1-x2)
            yd = abs(y1-y2)
            if xd>mind or yd>mind :
                continue
            d = xd*xd+yd*yd
            res = min(res,d)
            mind = math.sqrt(res)
    print(res)






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
points = []
distants = []
for _ in range(n):
    point = [int(_) for _ in input().split()]
    points.append(point)
for i in range(n):
    for j in range(n):
        if i != j:
            dis = (points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2
            distants.append(dis)
        else:
            pass
print(min(distants))

Submission status: Runtime Error

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 l<m:m=l
print(m)

Submission status: Runtime Error

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

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
  if m<l:m=(x-s)**2+(y-t)**2
print(m)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted([list(map(int,input().split()))for _ in[0]*n],key=lambda x:x[0])
m=1e9
for i in range(1,n):
 s,t=a[i]
 for x,y in a[:i][::-1]:
  if x-s>m:break
  m=min(m,(x-s)**2+(y-t)**2)
print(m)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=sorted([list(map(int,e.split()))for e in sys.stdin],key=lambda x:x[0])
m=1e9
for i in range(1,n):
 s,t=a[i]
 for x,y in a[:i][::-1]:
  if x-s>m:break
  m=min(m,(x-s)**2+(y-t)**2)
print(m)

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted([list(map(int,input().split()))for _ in[0]*n],key=lambda x:x[0])
m=1e9
for i in range(1,n):
 s,t=a[i]
 for x,y in a[:i][::-1]:
  if s-x>m:break
  m=min(m,(x-s)**2+(y-t)**2)
print(m)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=sorted([list(map(int,e.split()))for e in sys.stdin],key=lambda x:x[0])
m=1e9
for i in range(1,n):
 s,t=a[i]
 for x,y in a[:i][::-1]:
  if s-x>m:break
  m=min(m,(x-s)**2+(y-t)**2)
print(m)

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted([list(map(int,input().split()))for _ in[0]*n],key=lambda x:x[0])
m=1e9
for i in range(1,n):
 s,t=a[i]
 for x,y in a[:i][::-1]:
  if s-x>m:break
  if abs(t-y)<m:m=min(m,(x-s)**2+(y-t)**2)
print(m)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=sorted([list(map(int,e.split()))for e in sys.stdin.readlines()],key=lambda x:x[0])
m=1e9
for i in range(1,n):
 s,t=a[i]
 for x,y in a[:i][::-1]:
  if s-x>m:break
  if abs(t-y)<m:m=min(m,(x-s)**2+(y-t)**2)
print(m)

Submission status: Runtime Error

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(int(m+.1))

Submission status: Runtime Error

Solution code:
n=int(input())
a=[complex(*map(int,input().split()))for _ in[0]*n]
m=1e9
for i in range(1,n):
 z=a[i]
 for w in a[:i][::-1]:
  m=min(m,abs(w-z)**2)
print(int(m+.1))

Submission status: Runtime Error

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
  t=abs(w-z)**2
  if t<m:m=t
print(int(m+.1))

Submission status: Runtime Error

Solution code:
import sys
input()
a=sorted([complex(*map(int,e.split()))for e in sys.stdin],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
  t=abs(w-z)**2
  if t<m:m=t
print(int(m+.1))

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=sorted([complex(*map(int,e.split()))for e in sys.stdin],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
  t=abs(w-z)**2
  if t<m:m=t
print(int(m+.1))

Submission status: Runtime Error

Solution code:
import sys
def s():
 n=int(input())
 a=sorted([complex(*map(int,e.split()))for e in sys.stdin],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
   t=abs(w-z)**2
   if t<m:m=t
 print(int(m+.1))
if'__main__'==__name__:s()

Submission status: Runtime Error

Solution code:
import sys
def s(n):
 a=sorted([complex(*map(int,e.split()))for e in sys.stdin],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
   t=abs(w-z)**2
   if t<m:m=t
 print(int(m+.1))
if'__main__'==__name__:s(int(input()))

Submission status: Runtime Error

Solution code:
import sys
def s(n):
 t=[complex(*map(int,e.split()))for e in sys.stdin]
 a=sorted(t,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
   t=abs(w-z)**2
   if t<m:m=t
 print(int(m+.1))
if'__main__'==__name__:s(int(input()))

Submission status: Runtime Error

Solution code:
import sys
def s():
 n=int(input())
 a=sorted([complex(*map(int,e.split()))for e in sys.stdin],key=lambda x:x.real)
 m=1e9
 for i in range(1,n):
  z=a[i]
  for w in a[:i][::-1]:
   if (z-w).real>m:break
   t=abs(w-z)**2
   if t<m:m=t
 print(int(m+.1))
if'__main__'==__name__:s()

Submission status: Runtime Error

Solution code:
import sys
def s():
 n=int(input())
 a=sorted([complex(*map(int,e.split()))for e in sys.stdin],key=lambda x:x.real)
 m=1e9
 for i in range(1,n):
  z=a[i]
  t=z-w
  for w in a[:i][::-1]:
   if t.real>m:break
   d=abs(t)**2
   if d<m:m=d
 print(int(m+.1))
if'__main__'==__name__:s()

Submission status: Runtime Error

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(key = lambda x:x[1])
p.sort(key = lambda x:x[0])
mind = dist(0, 1)
minl = math.sqrt(mind)
for i in range(n):
    imax = bisect.bisect_right(p, (p[i][0] + minl , 0))
    for j in range(i + 1, imax):
        d = dist(i, j)
        if d < mind:
            mind = d
            minl = math.sqrt(mind)
print(mind)

Submission status: Runtime Error

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 + 1, 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: Runtime Error

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 i in range(n):
    p.append(tuple(list(map(int, input().split()))))
p.sort()
mind = dist(0, 1)
minl = math.sqrt(mind)
for i in range(n):
    for j in range(i + 1, 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: Runtime Error

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

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

print(minumundist(p))

Submission status: Runtime Error

Solution code:
import sys
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

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

print(minimumdist(p))

Submission status: Runtime Error

Solution code:
import numpy as np

Submission status: Runtime Error

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(round(min(b)**2))

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter
from itertools import permutations

def solve(a: list):
    length = len(a)
    if length <= 3:
        return min((p1[0]-p2[0])**2+(p1[1]-p2[1])**2 for p1, p2 in permutations(a, 2))

    x_set_len = len(set(x for (x, _) in a))
    axis = 0 if x_set_len > length/2 else 1
    a.sort(key=itemgetter(axis))
    mid_index = length//2
    left, right = a[:mid_index], a[mid_index:]
    delta = min(solve(left), solve(right))
    median = a[mid_index][axis]
    m_a = []
    append = m_a.append
        
    for p in left[::-1]:
        if p[axis] < median-delta:
            break
        append(p)
    for p in right:
        if p[axis] > median+delta:
            break
        append(p)
    m_a.sort(key=itemgetter(not axis))

    for i, p1 in enumerate(m_a):
        ub = p1[not axis] + delta
        for j, p2 in enumerate(m_a[i+1:]):
            if p2[not axis] > ub:
                break
            delta = min(delta, (p1[0]-p2[0])**2+(p1[1]-p2[1])**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: Runtime Error

Solution code:
def run():
    n = int(input())
    P = []
    for _ in range(n):
        P.append([int(i) for i in input().split()])

    d_min = 0
    for i in P:
        for j in P:
            if i == j:
                continue
            else:
                d = (i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2
                if d_min == 0 or d < d_min:
                    d_min = d

    print(d_min)

if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
n , p , d = input() , [] , "empty"
for x in range(n):
        p += [map(int,raw_input().split())]
for x in range(n):
        for y in range(n):
                dx = p[x][0] - p[y][0]
                dy = p[x][1] - p[y][1]
                if x < y and d == "empty":
                        d = dx**2+dy**2
                elif x < y:
                        d = min(d,dx**2+dy**2)
print(d)

Submission status: Runtime Error

Solution code:
n = input()
a = [map(int,raw_input().split()) for i in range(n)]
a.sort()
L = 10e20
for i in range(1, n-1):
       L = min(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: Runtime Error

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

Submission status: WA: Presentation 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(dist,'\n')

Submission status: WA: Presentation 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)+'\n')