쥐 잡기

시간 제한2초메모리 제한128 MB

요약

위치와 속도가 주어진 쥐들을 어느 시점에 정사각형 우리로 모두 가둘 수 없는 최대 변의 길이를 구하는 문제입니다.

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

문제

로봇 쥐들이 큰 2차원 보드 위를 움직이고 있다. 참가자는 변의 길이가 L인 정사각형 우리를 보드 위의 원하는 위치로 옮긴 뒤 떨어뜨릴 수 있다. 우리는 좌표축과 평행해야 하며 회전할 수 없다.

각 쥐는 처음 위치와 일정한 속도를 가진다. 게임이 시작된 직후부터 임의의 시각에 우리를 떨어뜨릴 수 있다. 어떤 쥐가 잡히려면 그 쥐가 우리 내부에 완전히 들어 있어야 한다. 경계 위에 있는 쥐는 잡힌 것으로 보지 않는다.

한 번에 모든 쥐를 절대로 잡을 수 없게 하는 가장 큰 L을 구하라.

입력

첫째 줄에 쥐의 수 N이 주어진다. N은 2 이상 50 이하이다.

다음 N개의 줄에는 각 쥐의 시작 위치와 속도 px py vx vy가 주어진다. 모든 값은 절댓값이 1,000 이하인 정수이다. 시작 위치가 (px, py)이고 속도가 (vx, vy)라면, t초 뒤의 위치는 (px + vx * t, py + vy * t)이다.

출력

정답을 한 줄에 출력한다. 절대 오차 또는 상대 오차가 10^-9 이하이면 정답으로 인정된다.

예제6

예제 1
입력
```
2
0 0 10 0
10 10 -10 0
```
예상 출력
```
10.0
```
예제 2
입력
```
3
0 0 1 4
10 0 -6 5
0 10 4 -4
```
예상 출력
```
3.0
```

예제 3

입력

4
50 -10 -5 40
10 30 -10 -10
30 20 -15 -1
15 40 -5 -50

예상 출력

40.526315789473685

예제 4

입력

예상 출력

10.0

예제 5

입력

5
13 20 4 1
50 20 50 1
100 -150 41 1
40 -40 -41 3
-100 63 -79 -1

예상 출력

212.78688524590163

예제 6
입력
```
2
0 0 5 3
10 0 5 3
```
예상 출력
```
10.0
```