Straight Lines 2

The distance from a line to a polygon is the smallest distance between that line and any point of the polygon. Here the polygon means both its boundary (its edges) and its interior. The polygon does not have to be convex: vertices may repeat and the boundary may cross itself.

Write a program that:

• reads a polygon and several lines from standard input,
• for each line computes the distance from that line to the polygon,
• writes the results to standard output.

The first line contains two integers $n$ and $m$ ($3 \le n \le 50\,000$, $1 \le m \le 50\,000$), separated by a space: the number of vertices of the polygon and the number of lines to analyze.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), the coordinates of the $i$-th vertex. Each pair of consecutive vertices, and also the last vertex together with the first, forms a side of the polygon.

Each of the next $m$ lines contains three integers $A_i$, $B_i$ and $C_i$ ($-10^9 \le A_i, B_i, C_i \le 10^9$, $A_i^2 + B_i^2 > 0$), describing the line $A_i x + B_i y + C_i = 0$.

Print $m$ lines. The $i$-th line must contain the square of the distance between the $i$-th line and the polygon, written as an irreducible fraction: the numerator, a / sign, then the positive denominator. If the line touches or crosses the polygon the distance is $0$, printed as 0/1.