삼각형 (CEOI 2009)

https://www.acmicpc.net/problem/3323

일전에 한번 멘붕이라고 언급한 적이 있었는데 (http://amugelab.tistory.com/entry/201573-2015723-problem-solving)

제대로 접근하면 아주 어렵지는 않다.

먼저 삼각형 쿼리를 뜯어보자. 한 점이 원점인 삼각형이면, 각도 범위 안에 있는 점들 중에서, 해당 선분 아래에 있는 점이 존재하는가? 를 묻는 문제가 됨을 알 수 있다.

그러면 각도 범위를 무력화하면 어떨까..? 그러면 꽤 유명한 문제다. (https://www.acmicpc.net/problem/7057) 들어오는 점 집합을 Convex Hull만 남겨두고, 이진 탐색을 하면 풀 수 있다. 복잡한 설명은 생략..

문제는 쿼리가 구간으로 들어온다는 점인데, 세그먼트 트리를 사용하자. 세그먼트 트리의 특징은 구간을 lgN개의 체인으로 끊어버릴 수 있다는 것이다. 앞서 한 체인에 대해서 lgN에 풀린다고 했으니 이 말대로면 쿼리당 lg^2N이다.

이제 세그먼트 트리를 initialize하는 게 문제이데, 한 점에 대응하는 구간 역시 lgN 개이다. 각 구간에 점을 넣고, 체인마다 convex hull algorithm을 돌리면 된다. NlgN에 빌드 할 수 있으며 대응하는 구간 * 점의 수는 NlgN이니 메모리 공간도 O(NlgN)이다.

설명이 좀 미흡한 거 같으니 소스를 붙인다. https://gist.github.com/koosaga/eacf5f73f9e1fb01b382

여담으로 학교 수행에 비슷한 문제를 냈었는데 다른 풀이가 있어서 좀 섭섭했다 ㅠㅠ (http://koistudy.net/?mid=prob_page&NO=1354 / https://www.acmicpc.net/problem/11001) 학교 정보 활동은 나중에 시간날때 한번에 정리할 예정.