주방 로봇

로봇은 점점 널리 쓰이고 있다. 이제는 공장뿐 아니라 가정에서도 로봇을 사용한다. 한 무리의 프로그래머들이 직접 가정용 로봇을 만들기로 했다. 파티가 끝나면 탁자 위에는 빈 병이 잔뜩 남는데, 이들은 로봇이 이 빈 병들을 치우도록 프로그래밍하기로 했다.

탁자는 너비가 w, 길이가 l인 직사각형이다. 로봇은 점 (xr, yr)에서 출발하며, 병 n개가 각각 점 (xi, yi) (i = 1, 2, ..., n)에 놓여 있다. 병 하나를 수거하려면 로봇은 그 병이 있는 지점으로 이동해 병을 집은 뒤, 탁자의 경계선 위 어느 한 점으로 가져가 버려야 한다. 로봇은 한 번에 병을 하나만 들 수 있으며, 제어 프로그램을 단순하게 하기 위해 병은 오직 탁자의 경계선 위에서만 내려놓을 수 있다.

로봇과 병의 크기는 무시할 수 있을 만큼 작아 모두 점으로 취급한다. 따라서 병을 든 로봇은 다른 병이 놓인 지점을 그대로 지나갈 수 있다.

제어 프로그램의 한 부분은 이동 경로를 계획한다. 로봇이 탁자 위의 모든 병을 수거하기 위해 이동해야 하는 경로의 최소 총 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 탁자의 너비 w와 길이 l을 나타내는 두 정수가 주어진다 (2 ≤ w, l ≤ 1000).

둘째 줄에 병의 개수를 나타내는 정수 n이 주어진다 (1 ≤ n ≤ 18).

이어지는 n개의 줄에는 각각 i번째 병의 좌표를 나타내는 두 정수 xi와 yi가 주어진다 (0 < xi < w, 0 < yi < l). 어떤 두 병도 같은 지점에 있지 않다.

마지막 줄에는 로봇의 시작 위치를 나타내는 두 정수 xr와 yr가 주어진다 (0 < xr < w, 0 < yr < l). 로봇의 시작 위치는 어떤 병과도 겹치지 않는다.

로봇 이동 경로의 최소 총 길이를 소수점 아래 정확히 6자리까지 반올림하여 한 줄에 출력한다 (예: %.6f 형식).