선분과 원의 미로

어느 괴짜 알고리즘 교수가 지독한 기말고사를 준비했다. 그는 학생들을 오직 직선 선분과 원으로만 이루어진 기묘한 미로 안에 떨어뜨린다. 이 미로의 교차점(junction)은 선분의 양 끝점과, 두 도형(선분 또는 원)이 서로 만나는 모든 교점이다.

교수는 미로 지도를 나눠 주고 정해진 시간을 잰다. 시간이 다 될 때까지 미로 안에 남아 있는 학생은 즉시 양자 수준에서 반전되어 버린다. 영리한 프로그래밍 전공 학생이라면 두 교차점 사이를 언제나 최단 경로로 이동한다는 것을 알기에, 교수는 학생이 이동해야 하는 거리가 최대한 길어지도록 입구와 출구 교차점을 고른다. 즉, 어떤 경로로든 연결된 모든 교차점 쌍 가운데, 두 점 사이의 최단 경로 길이가 가장 긴 쌍을 고른다.

이 "가장 긴 최단 경로"의 길이를 계산하는 일은 번거롭기 때문에, 교수는 그 일을 여러분에게 맡기려 한다. 선분과 원의 집합이 주어질 때, 모든 교차점 쌍 사이의 최단 경로를 구하고 그중 가장 긴 값을 출력하라.

미로 생성기는 다음을 보장한다.

1. 어떤 선분의 끝점도 원 위에 놓이지 않는다.
2. 어떤 선분도 원에 접하지 않는다.
3. 두 원이 만난다면, 서로 다른 정확히 두 점에서 만난다.
4. 모든 미로에는 교차점이 최소 두 개 있다(가장 작은 미로는 선분 하나이거나, 서로 만나는 두 원이다).

미로가 항상 하나로 연결되어 있는 것은 아니다. 일부 선분이나 원(또는 작은 부분 미로 전체)이 나머지와 떨어져 있을 수 있다. 여러분이 출력하는 길이는 반드시 실제로 연결된 두 교차점 사이의 경로여야 한다.

미로 형태의 예로는 다음이 있다. 선분만으로 이루어진 미로, 원만으로 이루어진 미로(이 경우 같은 최장 최단 경로 길이를 갖는 교차점 쌍이 둘 이상일 수 있다), 서로 떨어진 여러 덩어리로 나뉜 미로, 그리고 선분들이 원으로 이어져 더 긴 최단 경로가 생기는 미로.

각 테스트 케이스는 선분과 원의 집합이며, 한 줄에 도형 하나씩 주어진다.

• 선분은 L X1 Y1 X2 Y2 형식으로 주어진다. L은 글자 그대로의 문자이고, (X1, Y1)과 (X2, Y2)는 선분의 양 끝점이다.
• 원은 C X Y R 형식으로 주어진다. C는 글자 그대로의 문자이고, (X, Y)는 원의 중심, R은 반지름이다.

모든 값은 정수이다. 모든 선분과 원은 왼쪽 아래 (0, 0), 오른쪽 위 (100, 100)을 꼭짓점으로 하는 제1사분면의 정사각형 영역 안에 완전히 포함된다. 각 테스트 케이스는 1개 이상 20개 이하의 도형으로 이루어지며, 별표(*) 하나만 있는 줄로 끝난다. 마지막 테스트 케이스 다음에는, 별표 하나만 있는 줄이 한 번 더 나와 입력의 끝을 나타낸다.

각 미로에 대해 Case N: 을 출력한다. 여기서 N은 1부터 시작하는 테스트 케이스 번호이며, 그 뒤에 연결된 두 교차점 사이의 가장 긴 최단 경로 길이를 소수점 아래 한 자리로 반올림하여 출력한다.

호(arc)의 각을 계산할 때는 acos()나 asin()보다 atan2()를 사용하는 것이 좋다.