문제 링크 : www.acmicpc.net/problem/11738 문제 설명 다각형이 삼각분할 되어있다. 모든 선분의 길이는 1이다. 쿼리로 두 점이 주어졌을 때 두 점 사이의 거리를 출력하는 문제이다. 문제 태그 더보기 bfs, dnc, offline query, 재귀 문제 풀이 이 문제를 보면 가장 먼저 $O(NM)$ 의 풀이를 생각할 수 있다. 본인은 n개의 점에서 모두 다익스트라를 돌려서 $O(NMlgN)$의 풀이를 생각했지만 모든 선분의 가중치가 1이기 때문에 모든 점을 시작점으로 해서 각각 bfs를 하는 것으로 $O(NM)$의 풀이가 나오게 된다. 하지만 문제에서 요구하는 시간 복잡도는 제곱 미만이다. 따라서 이 문제의 특성을 관찰해야 한다. 이 문제의 가장 큰 특성은 일반적인 그래프가 아닌..