시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 256 MB 87 24 21 29.167%

문제

연돌이와 고잠녀는 유치원 시절부터 친한 친구였습니다.

하지만 한 순간의 잘못된 선택으로 인해 서로 만나기 힘들게 되었습니다.

신촌에서 안암으로 갈 수 있는 도로가 없기 때문입니다.

이를 딱하게 여긴 국토교통부 장관은 신촌에서 안암으로 갈 수 있는 도로를 하나 놓아주기로 했습니다.

하지만 재정상의 문제로 가능한 새로 설치해야 하는 도로의 길이를 짧게 하고 싶습니다.

2차원 평면 위에 신촌에 연결된 도로들의 정보와 안암에 연결된 도로들의 정보가 주어질 때, 신촌에서 안암으로 갈 수 있도록 해주는 가장 짧은 새 도로의 길이를 알려주세요.

입력

첫 줄에는 신촌에 연결된 도로의 숫자 n과 안암에 연결된 도로의 숫자 m(1 <= n, m <= 2,000)이 주어진다.

이어지는 n줄에 걸쳐 신촌에 연결된 도로의 정보가 (xs, ys), (xe, ye) 형태로 주어지며(-10,000 <= xs, ys, xe, ye <= 10,000, 좌표들은 실수) 이는 (xs, ys)와 (xe, ye)를 잇는 도로가 있다는 것을 뜻한다.

이어지는 m줄에 걸쳐 안암에 연결된 도로의 정보가 (xs, ys), (xe, ye) 형태로 주어지며(-50,000 <= xs, ys, xe, ye <= 50,000, 좌표들은 실수) 이는 (xs, ys)와 (xe, ye)를 잇는 도로가 있다는 것을 뜻한다.

신촌에 연결된 도로들은 어떠한 형태로 든 임의의 한 도로에서 다른 도로로 갈 길이 연결되어 있다는 것이 보장되고, 이는 안암에 연결된 도로끼리도 마찬가지이다.

그 어떤 신촌에 연결된 도로들도 안암에 연결된 도로와 닿아있지 않음 역시 보장된다.

연돌이는 신촌에서 도로 위를 통해서만 안암으로 향할 수 있다.

출력

신촌에서 안암으로 가기 위해 새로 놓아야 하는 최소 도로의 길이를 출력한다.

정답과 1e-6 미만의 상대/절대오차는 정답으로 인정한다.

예제 입력

2 1
-1.0 0.0 1.0 0.0
-1.0 1.0 1.0 -1.0
2.0 1.0 5.0 8.0

예제 출력

1.4142135623730951

힌트