포위 - SDS_PRO_9_5

문제 링크(koitp.org/problem/SDS_PRO_9_5/)

A나라와 B나라의 병사들에 대해 각각 컨벡스헐을 구한다.

그러면 A나라 컨벡스헐 내부에 있는 B나라의 병사 수와 B나라 컨벡스헐 내부에 있는 A나라의 병사 수를 구해야하는데, 편의상 전자에 대해서만 논하도록 하겠다.

A나라 컨벡스헐의 윗부분과 아랫부분을 나누어 생각해보자.

점 P가 A나라 컨벡스헐의 내부에 있다는 의미는 아래 1)과 2)를 모두 만족하는 것과 동치.

1) P가 윗부분 컨벡스헐에 대해 오른쪽에 있다.

2) P가 아랫부분 컨벡스헐에 대해 왼쪽에 있다.

따라서 A나라 컨벡스헐의 점들과 B나라 병사들 전부를 X좌표 순으로 오름차순 정렬해서 two-pointer 기법으로 처리하면 선형에 모든 병사들에 대한 처리가 가능하다. 만약 B나라 병사의 위치(X좌표)에 대응되는 어떠한 윗부분 컨벡스헐 선분 또는 아랫부분 컨벡스헐 선분이 없다면, 당연히 A나라 컨벡스헐 밖에 있다고 처리해주면 되겠다.

전체적인 시간복잡도는 따라서 O(N log N)이 된다. 그런데 저 문제는 데이터가 약해서 O(NM)으로도 맞는다.