직선 2

직선과 다각형 사이의 거리는 그 직선과 다각형에 속하는 임의의 점 사이의 거리 중 가장 작은 값이다. 여기서 다각형은 경계(변)와 내부를 모두 포함한다. 다각형은 볼록하지 않아도 되며, 같은 꼭짓점이 여러 번 나올 수 있고 경계가 스스로 교차할 수도 있다.

다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 다각형과 여러 개의 직선을 읽는다,
• 각 직선에 대해 그 직선과 다각형 사이의 거리를 계산한다,
• 결과를 표준 출력에 쓴다.

첫째 줄에 두 정수 $n$과 $m$ ($3 \le n \le 50\,000$, $1 \le m \le 50\,000$)이 공백으로 구분되어 주어진다. 각각 다각형의 꼭짓점 수와 분석할 직선의 수이다.

다음 $n$개의 줄에는 각각 두 정수 $x_i$와 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 주어지며, $i$번째 꼭짓점의 좌표이다. 이웃한 두 꼭짓점, 그리고 마지막 꼭짓점과 첫 번째 꼭짓점이 다각형의 변을 이룬다.

다음 $m$개의 줄에는 각각 세 정수 $A_i$, $B_i$, $C_i$ ($-10^9 \le A_i, B_i, C_i \le 10^9$, $A_i^2 + B_i^2 > 0$)가 주어지며, 직선 $A_i x + B_i y + C_i = 0$을 나타낸다.

$m$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 직선과 다각형 사이 거리의 제곱을 기약분수로 출력한다. 분자, / 기호, 양의 분모 순서로 쓴다. 직선이 다각형에 닿거나 다각형을 지나가면 거리는 $0$이며 0/1로 출력한다.