BOJ 14164: 삼각형 영역

Link

• https://www.acmicpc.net/problem/14164

• USACO 2016 December Platinum 1번

Tag

• 기하

Time Complexity

• $O(N^{3})$

점 N개가 있고, 이 중 3개를 택해 삼각형을 만들때 내부에 점이 i개 (0≤i≤N-3) 있는 삼각형의 갯수를 구해야 한다.

$O(N^{2})$ 개의 선분에 대해 왼쪽에 있는 점의 갯수를 ccw를 이용해 각각 $O(N)$, 총 $O(N^{3})$에 전처리한다.

 

cnt[i][j] = 선분 ij 왼쪽에 있는 점의 갯수 라고 하면, 삼각형 ABC 내부의 점의 갯수는 cnt[A][B], cnt[B][C], cnt[A][C]로 나타 낼 수 있다. 따라서 $O(N^{3})$ 개의 삼각형에 대해 내부의 점 갯수를 $O(1)$ 에 계산 할 수 있고, 총 시간복잡도 $O(N^{3})$ 에 문제를 해결할 수 있다.

Code