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][0], data[i][1]
angle_list =
for j in range(N):
if j != i:
x, y = data[j][0], data[j][1]
angle_list.append(angle)
return angle_list
answer = 0
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))
answer = max(answer, candidate)
print(answer)
- this is interesting, because we can know the most acute or most obtuse angle if we use this algorithm.
- we can generalize this. we can know the most similar angle to (XX°).
- XX=0, 30, 60, 90,...
- we can generalize this. we can know the most similar angle to (XX°).
- In the code I used Binary Search.
- Binary Search is useful when we want to know boundary.
- In this case, 1 domain is lesser than 180 degrees, the other domain is more than 180 degrees. So we can apply binary search.
- we should note that the array was monotoniously increasing sequence.
- When there are 3 variables, maybe we should fix 2nd (middle) one because middle one is often more special than 1st (or 3rd) one.
- Middle one was used to calculate list of angle.
- By generalizing this idea, fixing some special things (variables) is useful when there are many variables (when we have to consider many things).
Bye-bye!