IOI16 Aliens

https://oj.uz/problem/view/IOI16_aliens

최대 $k$개의 사진을 찍을 수 있을 때, 모든 흥미로운 위치를 포함하기 위한 최소 영역의 크기를 찾아야 한다.

일단 필요 없는 점을 제거하거나 $x$, $y$좌표가 서로 바뀌어도 동치라는 사실을 바탕으로 $x_i<x_{i+1}$, $y_i<y_{i+1}$, $x_i\leq y_i$를 만족하도록 흥미로운 위치를 정렬한다.

이 문제를 풀때 방해되는 것이 $k$가 사진의 장수를 제한하고 있다는 것이다.

방해되는 $k$를 치우기 위해 $k$값이 변화할 때 cost의 변화를 그려보면 위 그래프와 같이 감소하면서 볼록하다는 것을 관찰할 수 있다.

이 그래프에서 $x$좌표가 $k$값일 때 $y$좌표가 답이 된다.

그러나 아직 그래프의 각 점들의 좌표를 알 수가 없다.

여기서 이상한 생각을 할 수 있는데...

그래프의 접선의 기울기를 주면 (정확히는 접선이 아니지만 접선이라고 하자)

접점의 좌표를 알 수 있다는 것이다.

이것은 접선의 기울기를 $-c$라고 하면 $f(k)+ck$의 최솟값을 구하는 것과 같다.

$f(k)+ck$는 원래 문제에서 사진을 찍는 비용에 $c$원을 추가한 것과 같다.

접점 (k, )는 Convex Hull Trick을 이용하면 $O(n)$에 구할 수 있다.

이제 접선의 기울기가 감소하므로 최소($-m^2$)부터 최대($0$)까지 이분탐색을 통해 $x=k$인 점을 찾을 수 있다.

주의할 점은 여러 점들의 접선의 기울기가 같을 때는 그중 한 점의 좌표만 나온다는 것이다.

시간복잡도는 $O(nlogm)$이다.