아틀란티스 사건

문제

기원전 2222년 아틀란티스섬에서 끔찍한 참사가 일어났다. 하지만 이 사건은 오늘날까지 역사 기록으로만 전해지고, 물리적 증거를 찾은 사람은 아무도 없다. 이를 바로잡기 위해 켕 박사는 타임머신을 타고 참사 직전의 아틀란티스로 돌아가기로 했다.

신중한 켕 박사는 아틀란티스에 도착하자마자 시간 포털을 설치했다. 이 포털에 들어가면 곧바로 현재로 돌아올 수 있다. 탐사를 시작한 박사는 놀라운 사실을 발견했다. 아틀란티스는 원형 섬이고, 그 위에 매우 발달한 문명이 세워져 있었다. 섬 곳곳에 세워진 순간이동 네트워크의 부스가 그 증거다. 부스는 광선으로 작동하므로 출발 부스와 도착 부스 사이에 가로막히지 않은 시야가 있어야만 순간이동할 수 있다. 부스는 높이가 수십 미터에 이르는 섬에서 가장 웅장한 건축물에 속하며, 이보다 높은 것은 아틀란티스의 건국 이래 역사를 그린 거대한 벽화뿐이다. 벽화는 거대한 콘크리트 벽이다. 벽은 넘어갈 수 없어서 박사는 벽을 돌아서 가야 하고, 이 때문에 탐사가 쉽지 않다.

섬을 탐사하던 박사는 섬에 아무도 없다는 사실에 놀랐다. 한참 생각한 끝에 이유가 분명해졌다. 타임머신을 잘못 설정해서 아틀란티스를 무너뜨린 해일 바로 직전에 도착한 것이다(아틀란티스의 지질학자들은 이미 해일을 예측하고 섬에서 즉시 대피하라고 명령했다). 이 사실을 깨달은 박사는 곧바로 탈출 계획을 세웠다.

박사는 순간이동 부스를 이용해 시간 포털로 돌아가려 한다. 그런데 해일 때문에 전력 시스템이 버틸 수 있는 순간이동 횟수가 제한되어 있다. 박사가 시간 포털에 도착하기까지 걸어야 하는 최소 거리를 구해 주자.

박사는 섬 위를 자유롭게 걸을 수 있지만 벽을 가로질러 지나갈 수는 없다. 벽의 두께는 무시할 수 있으므로 벽의 끝점을 지나거나 벽을 따라 걷는 것은 허용된다.
순간이동 한 번은 한 부스에서 다른 부스로 이동하며, 걷는 거리에 포함되지 않는다. 두 부스를 잇는 선분이 어떤 벽과도 만나지 않을 때만 순간이동할 수 있다. 선분이 벽의 끝점에 닿기만 해도 시야가 가려진 것으로 본다.
순간이동은 모두 합해 최대 $T$ 번 할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 파일의 끝(EOF)까지 주어진다. 각 테스트 케이스의 첫째 줄에는 세 정수 $T$ , $M$ , $C$ 가 주어진다. 각각 순간이동 네트워크를 앞으로 사용할 수 있는 횟수, 아틀란티스에 있는 벽화의 수, 순간이동 부스의 수이다.

다음 $M$ 개의 줄에는 벽화가 주어진다. 벽화는 모두 선분이며, 각 줄에는 네 정수 $X_1$ , $Y_1$ , $X_2$ , $Y_2$ 가 주어진다. 이는 벽화 양 끝점의 좌표이다. 벽화의 두께는 무시할 수 있고, 어떤 두 벽화도 서로 만나지 않는다. 끝점에서 만나는 경우도 없다.

다음 $C$ 개의 줄에는 부스의 위치가 주어진다. 각 줄에는 두 정수 $X_C$ , $Y_C$ 가 주어지며, 이는 순간이동 부스 하나의 위치이다.

테스트 케이스의 마지막 줄에는 네 정수 $X_Q$ , $Y_Q$ , $X_P$ , $Y_P$ 가 주어진다. 각각 켕 박사의 시작 위치와 시간 포털의 좌표이다.

제한

$0 \le T, M, C \le 50$
입력으로 주어지는 모든 점의 좌표는 절댓값이 $2 \times 10^4$ 이하이다.
섬의 중심은 점 $(0, 0)$ 이고, 반지름은 $10^5$ 이다.
켕 박사의 위치, 시간 포털의 위치, 순간이동 부스의 위치는 모두 서로 다르며 벽화 위에 있지 않다.

출력

각 테스트 케이스마다 한 줄에 켕 박사가 포털까지 가기 위해 걸어야 하는 거리를 출력한다. 순간이동으로 이동한 거리는 포함하지 않는다. 거리는 소수점 아래 첫째 자리까지 반올림하여 출력한다(예: 8.1, 10.0).