GRAD
시간 제한2초메모리 제한256 MB
새 도시는 기존 도로 양 끝 도시와 두 도로로 연결되며 조회마다 두 도시 사이 최단 도로 거리를 출력합니다.
문제
도로망은 좌표 평면 위의 도시와, 두 도시를 잇는 직선 도로로 구성된다. 도로는 교차할 수 있지만, 다른 도로로 바꿔 탈 수 있는 곳은 그 도로가 연결한 두 도시뿐이다. 도로 길이는 두 도시 사이의 유클리드 거리다.
처음에는 도시 1과 2만 있고 서로 도로로 연결된다. 이후 각 단계에서 새 도시가 하나 추가되며, 그 순간 서로 도로로 직접 연결된 두 기존 도시 A, B와 각각 새 도로로 연결된다.
명령을 처리하는 프로그램을 작성한다.
d X Y A B: 좌표 에 새 도시를 추가하고, 그 순간 도로로 직접 연결된 A와 B에도 각각 도로로 연결한다.u A B: 두 도시 사이 최단 도로 거리를 출력한다.
입력
도시 1, 2의 좌표와 명령 수 이 주어진다. 각 명령은 d 또는 u 형식이다. 같은 좌표의 도시는 없다.
출력
각 u 명령에 대해 거리를 한 줄에 출력한다. 공식 정답과의 절대 오차는 이하여야 한다.