겹겹의 양파 껍질
다이아몬드 II의견: 0
평면 위에 \(N\)개의 점이 주어진다 (같은 좌표의 점이 여러 개 있을 수 있다). 다음 규칙에 따라 모든 점에 '껍질 번호'를 매긴다.
-
현재 남아 있는 점들의 볼록 껍질(convex hull)을 생각한다. 이 볼록 껍질의 경계 위에 있는 점들(꼭짓점뿐 아니라 변 위에 놓인 점, 즉 껍질 내부에 엄밀히 포함되지 않는 모든 점)에게 현재 껍질 번호를 부여한다.
-
번호를 받은 점들을 모두 제거한다.
-
껍질 번호를 \(1\) 증가시키고, 남은 점이 있으면 1번으로 돌아간다.
껍질 번호는 \(1\)부터 시작한다. 남은 점들이 모두 한 직선 위에 있거나 서로 다른 좌표가 \(2\)개 이하라면, 그 점들은 모두 같은 껍질 번호를 받고 제거된다. 같은 좌표의 점들은 항상 같은 껍질 번호를 받는다.
이렇게 정한 각 점의 껍질 번호 \(c_1, c_2, \dots, c_N\) (입력 순서)에 대한 체크섬을 출력한다. 체크섬은 \(M = 2^{61}-1\), \(h_0 = 0\), \(h_k = (h_{k-1} \cdot 1000003 + c_k) \bmod M\) 으로 계산한 \(h_N\) 이다.
\(1 \le N \le 100{,}000\)
\(-10^9 \le x_i, y_i \le 10^9\)
첫 줄에 점의 개수 \(N\)이 주어진다.
이어서 \(N\)개의 줄에 각 점의 좌표 \(x_i\), \(y_i\)가 주어진다.
껍질 번호 수열의 체크섬 \(h_N\) 한 개를 출력한다.
5
0 0
4 0
4 4
0 4
2 2
1168770150067166736정사각형 네 꼭짓점은 껍질1, 가운데 (2,2)는 껍질2. 껍질 번호 수열 [1,1,1,1,2]의 체크섬을 출력.
4
0 0
2 0
4 0
2 3
1000010000034000040삼각형 (0,0),(4,0),(2,3)의 변 (0,0)-(4,0) 위에 (2,0)이 놓여 있어 (2,0)도 껍질1에 포함된다. 네 점 모두 경계 위 -> 모두 껍질1. [1,1,1,1]의 체크섬.
riseoj 작성
출처 Original
평가 및 의견
겹겹의 양파 껍질
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
겹겹의 양파 껍질