ただのメモ

他の人に見せても良い方のメモ

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][0], data[i][1]
  angle_list = 
  for j in range(N):
    if j != i:
      x, y = data[j][0], data[j][1]
      angle = degrees(atan2(y-y_c, x-x_c))%360
      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,...
  • 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!