미술관 (KOI 2015 중등부 4번)

http://codeup.kr/JudgeOnline/problem.php?id=4854

데이터 만들기 어려워보이는 문제다 ㅠㅠ

일반성을 잃지 않고 s < e로 하자. 증명이 많은데 별로 안 엄밀함. (노력은 했다.)

서브태스크 2 (51점)

일단. 모든 점을 볼 수 있는 점이 하나라도 존재한다면, s -> e로 가는 최단 경로는 [s, e] 구간을 볼록하게 잇는 (오른쪽으로 계속 회전하는 방향의) 체인이 됨을 알 수 있다. 이는 컨벡스 헐과 동치이다.

증명 : 자명하게도, [s,e] 구간에 있는 점들만 고려해서 만든 convex chain보다 더 짧은 경로는 절대 만들 수 없다. 그 경로를 항상 만들 수 있음을 보일 것이다.

1. [s,e] 안에 있는 점들이 만약에 볼록 껍질 상 경로를 방해했다면. 볼록 껍질이라는 전제에 모순이 생긴다. 고로 이는 일어날 수 없다.

2. 이제 그 외의 점이 이 점을 건드릴 수 없음을 보일 것인데, 컨벡스 헐 상의 인접한 두 점 i, j(i < j)에 대해 (0, i, j) 점을 잇는 삼각형을 고려해보자. 앞의 가정을 만족하면서 (i, j) 간의 직선을 파괴하려면 (0, i) 나 (0, j) 상의 직선이 파괴되어야 하고, 그렇다면 모든 점이 볼 수 있다는 가정이 모순이다. 고로 최소 경로는 항상 가능하다.

3. i나 j가 0일 경우에는 자명히 직선으로 이으면 되니 컨벡스 헐이 역시 먹힌다.

만점

일단 위 51점 코드를 짰다면 여기서는 보통 WA가 나온다. 위쪽 마지막 문단의 증명을 검토하자.

1. 인접한 두 점 i, j가 같은 점에 의해 도달가능하면 증명은 동일하다.

2. i는 0번 점. j는 1번 점만 볼수 있다고 하자. 하지만 여전히 (i, j) 간 직선을 파괴하려면 (0, i) 나 (1, j)를 지나야만 한다. 다시 한번 가정에 모순. '

3. i나 j가 0 / 1일 경우는 케이스가 또 몇개 있다.

3 - 1. 둘다 0 - 1이면 자명하다.

3 - 2. 하나만 1이면, 만약 나머지 점이 0에 의해 도달가능하면 [1, j] 컨벡스헐. 아니면 1에 의해 도달 가능하니 자명하다.

3 - 3. 하나만 0이면, 만약 나머지 점이 1에 의해 도달가능하면 [j, 0] 컨벡스헐. 아니면 0에 의해 도달 가능하니 자명하다.

3-3 케이스를 처리하기 위해서. a(n) = a(0)으로 두고. 두 정점 중 하나가 0일 경우 무조건 n으로 바꿔두자. 그러면 풀린다.

cpp : https://gist.github.com/koosaga/a6f6c04fb5d22066cc0f