두 야수

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

요약

여러 직선으로 나뉜 평면에서 두 개의 매우 먼 고정점을 포함하는 두 볼록 영역 사이의 최소 거리의 제곱을 기약분수로 정확히 계산하는 문제입니다.

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

문제

아르데니아 대륙에는 아주 오래전부터 살아온 불꽃 야수와 얼음 야수가 있다. 두 야수는 각자의 서식지 근처에서만 지내도록 강력한 마법 직선들에 갇혀 있으며, 어떤 야수도 이 직선들을 넘을 수 없다. 만약 두 야수가 서로 너무 가까워지면 온 인류에게 재앙이 닥친다.

대륙은 무한히 넓은 평면으로 볼 수 있다. 얼음 야수의 서식지는 점 $(0, 10^{10})$ 에, 불꽃 야수의 서식지는 점 $(0, -10^{10})$ 에 있다. 즉 얼음 야수는 매우 위쪽에, 불꽃 야수는 매우 아래쪽에 자리한다. 평면 위에는 무한히 긴 직선 형태의 마법선이 여러 개 그어져 있고, 두 야수 모두 그 어떤 직선도 넘을 수 없다.

각 야수는 자신의 서식지를 포함하며 넘을 수 없는 직선들로 둘러싸인 영역 안에서만 자유롭게 돌아다닐 수 있다. 이 영역은 각 직선에 대해 그 야수의 서식지가 있는 쪽 반평면을 모두 교집합한 것으로, 볼록한 영역이 된다. 두 야수가 각각 도달할 수 있는 두 영역 사이의 최소 거리를 구하여라.

입력에는 여러 개의 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스의 개수 $Z$ $(Z \le 20)$ 가 주어지고, 이어서 $Z$ 개의 테스트 케이스가 아래에서 설명하는 형식으로 주어진다.

입력

각 테스트 케이스의 첫 줄에는 마법선의 개수 $n$ $(1 \le n \le 2 \cdot 10^5)$ 이 주어진다. 다음 $n$ 개의 줄에는 각각 공백으로 구분된 세 정수 $a, b, c$ $(-10^9 \le a, b, c \le 10^9,\ b \ne 0)$ 가 주어지며, 이는 직선 $ax + by + c = 0$ 을 나타낸다. $b \ne 0$ 이므로 모든 직선은 수직이 아니다.

출력

각 테스트 케이스마다 한 줄에, 두 영역 사이 최소 거리의 제곱을 기약분수 $p/q$ 형태로 출력한다. 이 값은 항상 유리수이다. $q \ge 1$ 이고 $\gcd(p, q) = 1$ 을 만족하도록 p/q를 출력한다. 예를 들어 정수 값 $v$ 는 v/1로, 거리가 $0$ 이면 0/1로 출력한다.

예제4

예제 1

입력

예상 출력

400/1
373/4

예제 2
입력
```
1
4
1 -1 0
1 1 0
0 1 -3
0 1 3
```
예상 출력
```
36/1
```
예제 3
입력
```
1
1
3 5 -7
```
예상 출력
```
0/1
```
예제 4
입력
```
1
2
0 1 -5
0 1 5
```
예상 출력
```
100/1
```