# Competitive Programing Typical 90 Problem day9

Day 9.

This problem wa hard for me.

There are 2 reasons.

First, I did not come up with the idea that integrates binary search to this problem.

Second, I stick to perpendicular line.

But now I get to the point.

Code is below.

N = int(input())
data = [ for _ in range(N)]
for j in range(N):
x,y = map(int,input().split())
data[j].append(x)
data[j].append(y)

from math import *
def AngleSort(i):
x_c , y_c = data[i], data[i]
angle_list =
for j in range(N):
if j != i:
x, y = data[j], data[j]
angle = degrees(atan2(y-y_c, x-x_c))%360
angle_list.append(angle)
return angle_list
for i in range(N):
angle_list = AngleSort(i)
angle_list.sort()
#i番目を中心として、偏角を並べる。
for j in range(N-1):
angle_now = angle_list[j]
l = 0
r = N-1
while r-l > 1:
mid = (l+r)//2
if (angle_list[(j + mid)%(N-1)] - angle_now)%360 <= 180:
l = mid
else:
r = mid
candidate1 = (angle_list[(j + l)%(N-1)] - angle_now)%360
candidate2 = (angle_list[(j + r)%(N-1)] - angle_now)%360
candidate = max(min(candidate1,360-candidate1),min(candidate2,360-candidate2))