https://www.acmicpc.net/problem/17399
문제 요약
- 트리가 주어졌을때 세 점의 외심이 있는지 없는지 판단.
- 외심 : 세점으로부터의 거리가 같음, 거리가 최소인 점
접근법
- 문제의 풀이가 존재하지만 다음과 같이 해결해봄(내 증명은 엄밀하진 않음. 출제자의 증명을 참고하는 것이 좋음)
- 출제자분의 증명 : https://cyberflower.github.io/2019/08/11/icpc17399.html
- 세 점중에서 가장 거리가 먼 두 점의 중점이 외심이 될 수 있을 것이고, 그 점에서 나머지 한 점의 거리를 구해서 외심인지 판단
- 간략한 증명
- 가장 먼 거리가 아닌 곳에는 있지 않을 것임(외심으로 인해 가장 먼 점의 거리가 더 줄어들 수 있으므로)
- 가장 먼 거리의 바깥(최단거리 바깥 점)에 있으면 줄여볼만한 여지가 있을 것임
- 다른 점들도 최단거리는 아닐테니..(최단거리였으면 그 거리가 가장 먼 거리일 것임)
- LCA를 구하고 이를 이용해 두 점의 거리 구할 수 있음
- 깊이가 더 깊은 곳에서 거리 / 2만큼 이동하면 중점이 나옴
- 중점에서 나머지 한 점의 거리를 구해서 외심인지 확인
newbieski