Total Circle

시간 제한1초메모리 제한256 MB

요약

점 집합 P와 Q가 주어질 때, Q의 점을 중심으로 P 전체를 포함하는 가장 작은 원들 가운데 반지름 제곱의 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 기하, 완전 탐색, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

좌표평면 위의 점 배열 $P = P_1, P_2, \cdots, P_N$ 과 $Q = Q_1, Q_2, \cdots, Q_M$ 이 있다. $Q$ 에 속한 한 점을 중심으로 하고 $P$ 에 속한 모든 점을 포함하는 최소 넓이의 원을 생각하자. 이 원의 반지름으로 가능한 값 중 최댓값을 구하시오.

입력

첫 줄에 $N$ 과 $M$ 이 주어진다. ($1 \le N, M \le 1000)

다음 $N$ 개의 줄에 걸쳐 $x$ 와 $y$ 가 주어지며, 이는 $P_i = (x, y)$ 라는 뜻이다. ($-10^6 \le x, y \le 10^6)

다음 $M$ 개의 줄에 걸쳐 $x$ 와 $y$ 가 주어지며, 이는 $Q_i = (x, y)$ 라는 뜻이다. ($-10^6 \le x, y \le 10^6)

출력

$Q$ 에 속한 한 점을 중심으로 하고 $P$ 에 속한 모든 점을 포함하는 최소 넓이의 원의 반지름으로 가능한 값 중 최댓값의 제곱을 출력한다.

예제2

예제 1
입력
```
1 1
0 0
1000000 1000000
```
예상 출력
```
2000000000000
```
예제 2
입력
```
4 4
2 6
3 1
1 7
8 9
4 3
5 2
9 6
6 4
```
예상 출력
```
65
```