| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 29 | 17 | 16 | 76.190% |
오늘도 서울과학고가 평화로운 것은 서울과학고를 지켜주는 혼문과 세 명의 헌터 덕분이다.
혼문은 $x$좌표와 $y$좌표가 모두 정수이고 1ドル\le x,y\le 10^{18}$인 모든 점 $(x,y)$로 이루어진 2ドル$차원 격자의 형태로 서울과학고 교정 전체를 덮는 거대한 방어막으로, 지하 마계에서 사악한 수행평가의 악마가 올라오는 것을 막고 있다. 세 명의 헌터는 영혼을 울리는 강력한 노래를 통해 혼문을 견고하게 유지한다.
어느 날, 사악한 귀마의 계략으로 서울과학고의 혼문에 $N$개의 균열이 생겼다. 각 균열은 혼문을 구성하는 격자점 중 정확히 하나의 점에 놓이며, 서로 위치가 중복될 수 있다. 이 균열들을 방치하면 위험해질 수 있기 때문에, 세 명의 헌터가 혼문 위 서로 다른 세 격자점에서 노래를 불러 균열을 제거하려고 한다. 다시 말해 세 헌터는 각각 $(X_1,Y_1),ドル $(X_2,Y_2),ドル $(X_3,Y_3)$ $(1\le X_i,Y_i\le 10^{18})$의 서로 다른 세 격자점에 배치되며, 균열이 있는 곳에 배치되는 것도 가능하다.
각 헌터는 자신이 배치된 점에서 노래를 부르고, $(X_i,Y_i)$에 서 있는 헌터의 노래는 다음 조건을 만족하는 모든 격자점 $(x,y)$에 도달한다.
\[|y-Y_i|\leq x-X_i\]
즉, 헌터의 노래는 아래 그림과 같이 $+x$축과 이루는 방향이 45ドル^{\circ}$ 이하인 모든 방향으로 퍼져 나간다.
노래의 힘은 매우 강력해서 모든 균열은 단 한 명의 헌터의 노래라도 도달하면 즉시 제거된다. 한 격자점 위에 여러 개의 균열이 있더라도 한 명의 헌터의 노래만 도달하면 모든 균열이 제거된다. 제거되지 않고 남는 균열의 개수가 최소가 되도록 세 명의 헌터를 배치할 때, 남은 균열의 개수를 구하여라.
첫째 줄에 균열의 수 $N$이 주어진다.
둘째 줄부터 $N$개의 줄에 걸쳐 $N$개의 균열의 위치가 주어진다. $i+1$번째 줄에 $i$번째 균열의 $x$좌표인 $x_i,ドル $y$좌표인 $y_i$가 공백으로 구분되어 주어진다.
첫째 줄에 세 명의 헌터를 배치하여 노래로 균열을 제거한 후 남은 균열의 개수의 최솟값을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | 모든 균열의 $x$좌표는 10ドル^9$ 미만이며, $y$좌표는 2ドル \times 10^9$의 배수이다. |
| 2 | 10 | $N \leq 50$ |
| 3 | 22 | $N \leq 2500$ |
| 4 | 59 | 추가 제한 조건이 없다. |
18 5 1 4 2 6 2 3 3 5 3 4 7 2 8 3 8 3 9 2 10 3 12 2 13 3 14 1 15 4 15 2 16 1 17 2 17
4
예제는 아래와 같이 $N=18$개의 균열이 생긴 경우이다. 이때, $(3, 3),ドル $(1, 9),ドル $(2, 13)$의 세 위치에 헌터를 배치할 경우, $(1, 15),ドル $(2, 16),ドル $(1, 17),ドル $(2, 17)$의 네 개의 균열을 제외한 모든 균열을 제거할 수 있다. 이보다 더 많은 균열을 제거할 수 있는 경우는 존재하지 않는다.
School > 서울과학고등학교 > SciOI 2025 G번