광교산 기슭에 자리를 잡고 서호를 바라보는 우리의 학교
서기 2067년, 송죽동에 천재지변이 발생하여 경기과학고등학교를 이전해야 하는 상황이 발생한다. 그러나 교가의 정신을 지키기 위해, 광교산과 서호는 아니더라도 산과 물이 가까이 있는 곳에 학교를 새로 짓고자 한다.
경기도는 무한한 2차원 좌표평면으로 표현할 수 있으며, 개의 산과 개의 물이 존재한다. 각 산과 물은 좌표평면 위의 점으로 나타낼 수 있다. 어떤 지점에서 가장 가까운 산까지의 유클리드 거리와 가장 가까운 물까지의 유클리드 거리를 더한 값을 그 지점의 점수라고 하자. 이때 점수가 최소가 되는 지점들 중 한 곳을 잡아 그곳에 학교를 건설하려 한다.
여러분은 2067년 경기과학고등학교 교장 김명준을 도와 학교의 새 위치를 결정해야 한다. 점수가 최소가 되도록 할 때, 그 점수는 얼마인가?
첫 번째 줄에 두 양의 정수 , 이 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄 중 번째 줄에 번째 산의 좌표 와 좌표 가 공백으로 구분되어 주어진다.
다음 개의 줄 중 번째 줄에 번째 물의 좌표 와 좌표 가 공백으로 구분되어 주어진다.
첫 번째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 까지 허용한다.
실제 정답이 , 출력한 정답이 일 때, 절대 오차는 , 상대 오차는 로 정의한다. 절대 오차와 상대 오차 중 하나라도 보다 작거나 같으면 정답으로 인정한다.
