Constellation 2 (JOI 2014 Spring Camp)

http://oj.uz/problems/view/JOI14_constellation2

삼각형 하나를 잡고 나머지 삼각형을 빠르게 세는..? 류의 방법으로 계속 시도를 해봤는데 진전이 별로 없었다.

실제 풀이는 굉장히 중요한 2개의 lemma에 의존하는데,

 * 1. 교차하지 않는 삼각형 쌍에 대해서, 두 삼각형을 완전히 분리시키는 직선이 항상 존재한다.

 * 2. 교차하지 않는 삼각형 쌍에 대해서, 삼각형 1의 점 - 삼각형 2의 점을 잇는 두 직선을 고려해 보자. (경우의 수는 9개). 이 중 두 삼각형을 완전히 분리시키는 직선이 항상 2개 존재한다.

Lemma 1이 상당히 감명깊었다. 삼각형 쌍을 분리하는 법을 깔끔하게 정의한 것도 그렇고, (자명하지 않은) Lemma 2와 엮어서 실제로 문제를 깔끔하게 풀어내는 것도 놀라웠다.

아무튼 이를 통해 자명한 N^3 알고리즘을 유도할 수 있다. 직선 하나를 잡고, 왼쪽 오른쪽에 있는 0 / 1 / 2 점의 수를 세주면 그에 따른 삼각형의 개수를 알 수 있으니, 이렇게 구한 삼각형의 개수 합을 2로 나눈 것을 출력하면 된다. 이를 각도 정렬 등으로 최적화시키면 O(N^2lgN) 알고리즘을 유도할 수 있다.

JOI 문제들 중에 "한가지 중요한 관찰을 하면 쉽게 풀리는" 문제들이 꽤 있다. Open Contest 2014 (https://www.acmicpc.net/category/detail/1464)의 Pinball / Fortune Telling 2가 대표적인 문제라고 생각을 하는데.. 이 문제는 저 예시들보다는 훨씬 어려운 류에 속하는 거 같다.