Problem:


最古の遺跡  

問題

 昔, そこには集落があり, 多くの人が暮らしていた. 人々は形も大きさも様々な建物を建てた. だが, それらの建造物は既に失われ, 文献と, 遺跡から見つかった柱だけが建造物の位置を知る手がかりだった.

 文献には神殿の記述がある. 神殿は上から見ると正確に正方形になっており, その四隅には柱があった. 神殿がどの向きを向いていたかはわからない. また, 辺上や内部に柱があったかどうかもわからない. 考古学者たちは, 遺跡から見つかった柱の中で, 正方形になっているもののうち, 面積が最大のものが神殿に違いないと考えた.

 柱の位置の座標が与えられるので, 4 本の柱でできる正方形のうち面積が最大のものを探し, その面積を出力するプログラムを書け. なお, 正方形の辺は座標軸に平行とは限らないことに注意せよ.

例

 下の図の例では, 10 本の柱があり, 座標 (4, 2), (5, 2), (5, 3), (4, 3) にある 4 本と座標 (1, 1), (4, 0), (5, 3), (2, 4) にある 4 本が正方形をなしている. 面積が最大の正方形は後者で, その面積は 10 である.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロ１つを含む行で終了する．

1 行目には, 遺跡から見つかった柱の本数 n が書かれている.

 2 行目から n + 1 行目までの n 行の各々には, 柱の x 座標と y 座標が空白区切りで書かれている.

 1 本の柱が 2 度以上現れることはない.

 n は 1 ≤ n ≤ 3000 を満たす整数であり, 柱の x 座標と y 座標は 0 以上 5000 以下の整数である.

 採点用データのうち, 配点の 30% 分は 1 ≤   n ≤ 100 を満たし, 配点の 60% 分は1 ≤ n ≤ 500 を満たす.

データセットの数は 10 を超えない．

出力

データセットごとに 1 個の整数を出力する. 4 本の柱からなる正方形が存在する場合は, そのような正方形のうち面積が最大のものの面積を出力し, そのような正方形が存在しない場合は 0 を出力せよ.

入出力例

入力例

10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
0

出力例

10
10

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



Sample input:
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
0


Sample output:
10
10

Submission status: Wrong Answer

Solution code:
n = int(input())

poles = [tuple(map(int, input().split())) for _ in range(n)]
poles_set = set(poles)

max_square = 0
for i in range(n):
    x1, y1 = poles[i]
    for j in range(i, n):
        x2, y2 = poles[j]
        dx, dy = x2 - x1, y2 - y1
        if ((x2 + dy, y2 - dx) in poles_set and (x1 + dy, y1 - dx) in poles_set) \
                or ((x2 - dy, y2 + dx) in poles_set and (x1 - dy, y1 + dx) in poles_set):
            edge = dx ** 2 + dy ** 2
            if max_square < edge:
                max_square = edge
print(max_square)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = input()
    if n == 0: break
    p = [map(int, raw_input().split()) for i in range(n)]
    ans = 0
    for i in range(n):
        for j in range(i,n):
            x  = p[j][0]
            y  = p[j][1]
            mx = x - p[i][0]
            my = y - p[i][1]
            if [x+my, y-mx] in p:
                if [x+my-mx, y-mx-my] in p:        
                    ans = max(ans, mx**2 + my**2)
    print ans

Submission status: Time Limit Exceeded

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        Plist=[]
        for i in range(n):
            [x,y]=[int(x) for x in raw_input().split()]
            Plist.append((x,y))
        Plist.sort(key=lambda(x):x[0])
        ans=0
        for p in range(n):
            for q in range(p,n):
                (px,py)=Plist[p]
                (qx,qy)=Plist[q]
                xdist=px-qx
                ydist=py-qy
                fugou=[1,-1]
                for f in fugou:
                    if (px-f*ydist,py+f*xdist) in Plist and (qx-f*ydist,qy+f*xdist) in Plist:
                        ans=max(ans,xdist**2+ydist**2)
        print ans

Submission status: Time Limit Exceeded

Solution code:
import bisect

def birange(Plist,x,Pxlist):
    l=bisect.bisect_left(Pxlist,x)
    r=bisect.bisect_right(Pxlist,x)
    return Plist[l:r+1]


while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        Plist=[]
        Pxlist=[]
        for i in range(n):
            [x,y]=[int(x) for x in raw_input().split()]
            Plist.append((x,y))
            Pxlist.append(x)
        Plist.sort(key=lambda(x):x[0])
        Pxlist.sort()
        ans=0
        for p in range(n):
            for q in range(p,n):
                (px,py)=Plist[p]
                (qx,qy)=Plist[q]
                xdist=px-qx
                ydist=py-qy
                fugou=[1,-1]
                for f in fugou:
                    if (px-f*ydist,py+f*xdist) in birange(Plist,px-f*ydist,Pxlist) and (qx-f*ydist,qy+f*xdist) in birange(Plist,px-f*ydist,Pxlist):
                        ans=max(ans,xdist**2+ydist**2)
        print ans

Submission status: Time Limit Exceeded

Solution code:
while True:
    n=int(input())
    if n==0:break
    pil=[[int(s)for s in input().split(" ")]for i in range(n)]
    mS=0
    i=0
    while i<n:
        j=1
        while i+j<n:
            x1,y1=pil[i]
            x2,y2=pil[i+j]
            s=x2-x1
            t=y2-y1
            if [x1-t,y1+s] in pil and [x2-t,y2+s] in pil:mS=max((mS,s**2+t**2))
            if [x1+t,y1-s] in pil and [x2+t,y2-s] in pil:mS=max((mS,s**2+t**2))
            j+=1
        i+=1
    print(mS)

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	xy = [map(int,raw_input().split()) for i in range(n)]
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			dx,dy = x2-x1,y2-y1
			if [x1-dy,y1-dx] in xy and [x2+dy,y2-dx] in xy:
				ans = max(ans,dx**2+dy**2)
			if [x1-dy,y1+dx] in xy and [x2-dy,y2+dx] in xy:
				ans = max(ans,dx**2+dy**2)
	print ans

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	x,y = xy[0]
	xy = sorted(xy, key = lambda XY:(XY[0]-x)**2 + (XY[1]-y)**2)
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		for j in range(n-3,i,-1):
			x2,y2 = xy[j]
			dx,dy = x2-x1,y2-y1
			if [x1-dy,y1-dx] in xy[j+1:] and [x2+dy,y2-dx] in xy[j+1:]:
				ans = dx**2+dy**2
			if [x1-dy,y1+dx] in xy[j+1:] and [x2-dy,y2+dx] in xy[j+1:]:
				ans = dx**2+dy**2
			if ans: break
		if ans: break
	print ans

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	x,y = xy[0]
	xy = sorted(xy, key = lambda XY:(XY[0]-x)**2 + (XY[1]-y)**2)
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		for j in range(n-3,i,-1):
			x2,y2 = xy[j]
			dx,dy = x2-x1,y2-y1
			if [x1-dy,y1-dx] in xy[j+1:j+501] and [x2+dy,y2-dx] in xy[j+1:j+501]:
				ans = dx**2+dy**2
			if [x1-dy,y1+dx] in xy[j+1:j+501] and [x2-dy,y2+dx] in xy[j+1:j+501]:
				ans = dx**2+dy**2
			if ans: break
		if ans: break
	print ans

Submission status: Time Limit Exceeded

Solution code:
p = 100
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	x,y = xy[0]
	xy = sorted(xy, key = lambda XY:(XY[0]-x)**2 + (XY[1]-y)**2)
	ans = 0
	for i in range(n-4):
		x1,y1 = xy[i]
		for j in range(n-3,i,-1):
			x2,y2 = xy[j]
			dx,dy = x2-x1,y2-y1
			if [x1-dy,y1-dx] in xy[j+1:j+p] and [x2+dy,y2-dx] in xy[j+1:j+p]:
				ans = dx**2+dy**2
			if [x1-dy,y1+dx] in xy[j+1:j+p] and [x2-dy,y2+dx] in xy[j+1:j+p]:
				ans = dx**2+dy**2
			if ans: break
		if ans: break
	print ans

Submission status: Time Limit Exceeded

Solution code:
p = 50
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	x,y = xy[0]
	xy = sorted(xy, key = lambda XY:(XY[0]-x)**2 + (XY[1]-y)**2)
	ans = 0
	for i in range(n-4):
		x1,y1 = xy[i]
		for j in range(n-3,i,-1):
			x2,y2 = xy[j]
			dx,dy = x2-x1,y2-y1
			if [x1-dy,y1-dx] in xy[j+1:j+p] and [x2+dy,y2-dx] in xy[j+1:j+p]:
				ans = dx**2+dy**2
			if [x1-dy,y1+dx] in xy[j+1:j+p] and [x2-dy,y2+dx] in xy[j+1:j+p]:
				ans = dx**2+dy**2
			if ans: break
		if ans: break
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	dxy = [[xy1[0]-xy2[0],xy1[1]-xy2[1]] for xy1,xy2 in itertools.combinations(xy,2)]
	for dx,dy in dxy:
		if dxy.count([dx,dy]) > 1 and (dxy.count([dy,-dx]) > 1 or dxy.count([-dy,-dx]) > 1):
			print dx**2+dy**2
			break
	else:
		print 0

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	dxy = [[xy1[0]-xy2[0],xy1[1]-xy2[1]] for xy1,xy2 in itertools.combinations(xy,2)]
	for i in range(len(dxy)-1,-1,):
		if dxy.count(dxy[i]) < 2: del dxy[i]
	dxy = sorted(dxy, key = lambda d:d[0]**2 + d[1]**2, reverse = True) 
	for dx,dy in dxy:
		if dxy.count([dy,-dx]) > 1 or dxy.count([-dy,-dx]) > 1:
			print dx**2 + dy**2
			break
	else:
		print 0

Submission status: Accepted

Solution code:
while 1:
    n = input()
    if n == 0: break
    p = set([tuple(map(int, raw_input().split())) for i in range(n)])
    ans = 0
    for x1, y1 in p:
        for x2, y2 in p:
            mx = x2 - x1
            my = y2 - y1
            if mx==0 and my==0: continue
            if (x2+my, y2-mx) in p:
                if(x2+my-mx, y2-mx-my) in p:
                    ans = max(ans, mx**2 + my**2)
    print ans

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if not n:
        break

    poles = [tuple(map(int, input().split())) for _ in range(n)]
    poles_set = set(poles)

    max_square = 0
    for i in range(n):
        x1, y1 = poles[i]
        for j in range(i, n):
            x2, y2 = poles[j]
            dx, dy = x2 - x1, y2 - y1
            if ((x2 + dy, y2 - dx) in poles_set and (x1 + dy, y1 - dx) in poles_set) \
                    or ((x2 - dy, y2 + dx) in poles_set and (x1 - dy, y1 + dx) in poles_set):
                edge = dx ** 2 + dy ** 2
                if max_square < edge:
                    max_square = edge
    print(max_square)

Submission status: Accepted

Solution code:
def main():
  #points = [[False for i in range(5001)] for j in range(5001)]
  while True:
    n = int(input())
    if not n:
      break
    ps = []
    dic = {}

    for i in range(n):
      x, y = map(int,input().split())
      dic[(x, y)] = 1;
      #points[x][y] = True
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        vx = p2[0] - p1[0]
        vy = p2[1] - p1[1]
        #if  0 <= p1[0] + vy <= 5000 and 0 <= p1[1] - vx <= 5000 and 0 <= p2[0] + vy <= 5000 and 0 <= p2[1] - vx <= 5000:
        #  if  points[p1[0] + vy][p1[1] - vx] and points[p2[0] + vy][p2[1] - vx]:
        if (p1[0] + vy, p1[1] - vx) in dic and (p2[0] + vy, p2[1] - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    
    #for p in ps:
    #  points[p[0]][p[1]] = False

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
  while True:
    n = int(input())
    if not n:
      break
    ps = []
    dic = {}

    for i in range(n):
      x, y = map(int,input().split())
      dic[(x, y)] = 1;
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        p1x = p1[0]
        p1y = p1[1]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy, p1y - vx) in dic and (p2x + vy, p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
  while True:
    n = int(input())
    if not n:
      break
    ps = [list(map(int,input().split())) for i in range(n)]
    dic = set()
    for t in ps:
      dic.add((t[0],t[1]))
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        p1x = p1[0]
        p1y = p1[1]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy, p1y - vx) in dic and (p2x + vy, p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
  while True:
    n = int(input())
    if not n:
      break
    ps = [list(map(int,input().split())) for i in range(n)]
    dic = set()
    for t in ps:
      dic.add((t[0],t[1]))
    ans = 0
  
    for i in range(n):
      p1 = ps[i]
      p1x = p1[0]
      p1y = p1[1]
      for j in range(n):
        p2 = ps[j]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy, p1y - vx) in dic and (p2x + vy, p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()

Submission status: Accepted

Solution code:
def main():
  while True:
    n = int(input())
    if not n:
      break
    ps = [tuple(map(int,input().split())) for i in range(n)]
    dic = set()
    for t in ps:
      dic.add(t)
    ans = 0
  
    for i in range(n):
      p1 = ps[i]
      p1x = p1[0]
      p1y = p1[1]
      for j in range(n):
        p2 = ps[j]
        p2x = p2[0]
        p2y = p2[1]
        vx = p2x - p1x
        vy = p2y - p1y
        if (p1x + vy , p1y - vx) in dic and (p2x + vy , p2y - vx) in dic:
          ans = max(ans, vx ** 2 + vy ** 2)
    

    print(ans)
main()

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == 0: break
    P = set(tuple(map(int, raw_input().split())) for i in range(n))
    ans = 0
    for xi, yi in P:
        for xj, yj in P:
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in P and r in P:
                ans = max(ans, pow(xi - xj, 2) + pow(yi - yj, 2))
    print ans

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == 0: break
    P = set(tuple(map(int, raw_input().split())) for i in range(n))
    ans = 0
    for xi, yi in P:
        for xj, yj in P:
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in P and r in P:
                ans = max(ans, (xi - xj) ** 2 + (yi - yj) ** 2)
    print ans

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == 0: break
    P = [(map(int, raw_input().split())) for i in range(n)]
    S = set(map(tuple, P))
    ans = 0
    for i in range(n - 1):
        xi, yi = P[i]
        for j in range(i + 1, n):
            xj, yj = P[j]
            q = (xj - yj + yi, yj + xj - xi)
            r = (xi - yj + yi, yi + xj - xi)
            if q in S and r in S:
                ans = max(ans, (xi - xj) ** 2 + (yi - yj) ** 2)
    print ans

Submission status: Accepted

Solution code:
p = 100
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		xy = xy[:i] + sorted(xy[i:], key = lambda XY:(XY[0]-x1)**2 + (XY[1]-y1)**2)
		cur = 0
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				cur = (x1-x2)**2 + (y1-y2)**2
				break
		ans = max(ans,cur)
	print ans

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	xy = [map(int,raw_input().split()) for i in range(n)]
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				ans = max(ans,(x1-x2)**2 + (y1-y2)**2)
	print ans

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	xy = [map(int,raw_input().split()) for i in range(n)]
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n-1):
		x1,y1 = xy[i]
		for j in range(i+1,n):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				ans = max(ans,(x1-x2)**2 + (y1-y2)**2)
	print ans

Submission status: Runtime Error

Solution code:
  points = [[False for i in range(5001)] for j in range(5001)]
  ps = []

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

  ans = 0

  for i in range(n):
    for j in range(n):
      p1 = ps[i]
      p2 = ps[j]
      vx = p2[0] - p1[0]
      vy = p2[1] - p1[1]
      p3 = p1[0] + vy, p1[1] - vx
      if points[p1[0] + vy][p1[1] - vx] and points[p2[0] + vy][p2[1] - vx]:
        ans = max(ans, vx ** 2 + vy ** 2)

  print(ans)

Submission status: Runtime Error

Solution code:
def main():
  while True:
    n = int(input())
    if not n:
      break
    points = [[False for i in range(5001)] for j in range(5001)]
    ps = []
  
    for i in range(n):
      x, y = map(int,input().split())
      points[x][y] = True
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        vx = p2[0] - p1[0]
        vy = p2[1] - p1[1]
        if  0 <= p1[0] + vy <= 5000 and 0 <= p1[1] - vx <= 5000 and 0 <= p2[0] + vy <= 5000 and 0 <= p2[1] - vx <= 5000:
          if  points[p1[0] + vy][p1[1] - vx] and points[p2[0] + vy][p2[1] - vx]:
            ans = max(ans, vx ** 2 + vy ** 2)
  
    print(ans)
main()

Submission status: Runtime Error

Solution code:
def main():
  points = [[False for i in range(5001)] for j in range(5001)]
  while True:
    n = int(input())
    if not n:
      break
    ps = []

    for i in range(n):
      x, y = map(int,input().split())
      points[x][y] = True
      ps.append((x,y))
  
    ans = 0
  
    for i in range(n):
      for j in range(n):
        p1 = ps[i]
        p2 = ps[j]
        vx = p2[0] - p1[0]
        vy = p2[1] - p1[1]
        if  0 <= p1[0] + vy <= 5000 and 0 <= p1[1] - vx <= 5000 and 0 <= p2[0] + vy <= 5000 and 0 <= p2[1] - vx <= 5000:
          if  points[p1[0] + vy][p1[1] - vx] and points[p2[0] + vy][p2[1] - vx]:
            ans = max(ans, vx ** 2 + vy ** 2)
    
    for p in ps:
      points[p[0]][p[1]] = False

    print(ans)
main()

Submission status: Runtime Error

Solution code:
import sys
from copy import deepcopy

#fp = open("input.txt", "r")
fp = sys.stdin

while True:
    n = int(fp.readline()[:-1])
    if n == 0:
        break

    li = []
    for i in xrange(n):
        element = map(int, fp.readline()[:-1].split(" "))
        li.append(element)

    ret = 0
    for i in xrange(n):
        element = li.pop(0)
        cloned = deepcopy(li)
        for j in xrange(n-1):
            cloned[j][0] -= element[0]
            cloned[j][1] -= element[1]
            cloned[j].append(cloned[j][0]*cloned[j][0]+cloned[j][1]*cloned[j][1])
        cloned.sort(key=lambda x:x[2])
        for j in xrange(n-2):
            if cloned[j][2] == cloned[j+1][2]:
                key = [cloned[j][k]+cloned[j+1][k] for k in xrange(3)]
                if key in cloned:
                    if cloned[j][2] > ret:
                        ret = cloned[j][2]
        li.append(element)
    print ret

Submission status: Runtime Error

Solution code:
import sys

#fp = open("input.txt", "r")
fp = sys.stdin

while True:
    n = int(fp.readline()[:-1])
    if n == 0:
        break

    li = []
    for i in xrange(n):
        element = map(int, fp.readline()[:-1].split(" "))
        li.append(element)

    ret = 0
    for i in xrange(n):
        element = li.pop(0)
        cloned = [li[j][:] for j in xrange(n-1)]
        
        for j in xrange(n-1):
            cloned[j][0] -= element[0]
            cloned[j][1] -= element[1]
            cloned[j].append(cloned[j][0]*cloned[j][0]+cloned[j][1]*cloned[j][1])
        cloned.sort(key=lambda x:x[2])
        for j in xrange(n-2):
            if cloned[j][2] == cloned[j+1][2]:
                key = [cloned[j][k]+cloned[j+1][k] for k in xrange(3)]
                if key in cloned:
                    if cloned[j][2] > ret:
                        ret = cloned[j][2]
        li.append(element)
    print ret

Submission status: Runtime Error

Solution code:
p = 50
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	x1,y1 = xy[0]
	xy = sorted(xy, key = lambda XY:(XY[0]-x1)**2 + (XY[1]-y11)**2)
	ans = 0
	for j in range(n-3,0,-1):
		x2,y2 = xy[j]
		dx,dy = x2-x1,y2-y1
		if [x1-dy,y1-dx] in xy[j+1:j+p] and [x2+dy,y2-dx] in xy[j+1:j+p]:
			ans = dx**2+dy**2
		if [x1-dy,y1+dx] in xy[j+1:j+p] and [x2-dy,y2+dx] in xy[j+1:j+p]:
			ans = dx**2+dy**2
		if ans: break
	print ans

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	xy = [map(int,raw_input().split()) for i in range(n)]
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n):
		x1,y1 = xy[i]
		for j in range(n-1,i,-1):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				ans = max((x1-x2)**2 + (y1-y2)**2)
	print ans