ACM ICPC 2016 인터넷 예선 E번

1. 한 다각형 P(k)를 어떤 선분 L(k)로 치환하는데 L(k)를 구성하는 두 점은, P(k)를 구성하는 점들 중 원점으로부터 각도 최소인 점과 최대인 점

2. L들을 각도순으로 본다.

2-1. L에서 선분의 시작이면, 힙에다가 해당 선분을 넣음.

2-2. L에서 선분의 끝이면, 힙에서 해당 선분을 삭제함.

  2-2-1. 힙의 중간 부분에 있는 원소이면, 힙의 마지막 원소랑 해당 번째랑 자리를 바꾸고, 올릴 수 있는 만큼 올리고, 내려갈 수 있는 만큼 내려보냄.

  2-2-2. 힙의 끝에 있는 원소이면, 힙의 사이즈만 줄이면 됨.

  어떤 단위 각도 구간에 대해서 원점에 가까운 선분 L1은 원점에 보다 먼 선분 L2보다 이후의 구간에서 계속 더 가까운 성질을 이용하면 된다.

  이 성질이 성립하는 이유는 교차하는 선분(다각형)이 존재하지 않기 때문이다. 힙의 우선순위 기준은 원점과 이은 선분의 교차 판정으로 할 수 있다.

3. 매 단위 각도 구간에 대해서 현재 가장 원점과 가까운 다각형은 보인다고 표시해준다.

4. 모든 단위 각도 구간에 대해서 다 처리했으면 표시 되지 않은 다각형의 개수를 답으로 출력한다.