Polygon and Lines

Time limit0.5sMemory limit128 MB

Summary

For each line crossing a convex polygon, find the closest polygon vertex to the line and print the distance.

Level: Medium7 of 10
Topics: Geometry, Binary search
Solved: No attempts yet

Problem

Gustav likes to solve geometry problems. While browsing geometry problems on the internet he ran into one he could not solve on his own, so help him solve the following problem.

You are given one convex polygon and several lines that cross it. For each line, find the vertex of the polygon closest to that line and compute the distance between the line and that vertex.

A line crosses the polygon if it has at least one point in common with the interior of the polygon.

Input

The first line contains the number of vertices of the polygon $N$ ( $3 \le N \le 100\,000$ ).

Each of the next $N$ lines holds the coordinates of one vertex of the convex polygon: two integers whose absolute value is smaller than $10^9$ . The vertices are given in clockwise order.

The next line contains the number of lines $M$ ( $1 \le M \le 100\,000$ ).

Each of the next $M$ lines holds three integers $A$ , $B$ , $C$ that describe the line $Ax + By + C = 0$ . Here $|A|, |B|, |C| \le 10^9$ , and $A$ and $B$ are never both $0$ . Every given line crosses the polygon.

Output

Print $M$ lines. Line $i$ holds the distance between line $i$ and the closest vertex of the polygon, rounded to three decimal places.

Examples4

Example 1
Input
```
4
0 2
2 0
0 -2
-2 0
1
0 4 -5
```
Expected output
```
0.750
```

Example 2

Input

Expected output

0.224
2.000

Example 3

Input

4
0 0
0 10
10 10
10 0
6
1 1 -5
1 -1 -3
0 1 -7
1 0 -4
1 -1 0
1000000 1 -1

Expected output

Example 4

Input

5
-1000 -1000
-900 800
500 1000
1000 -200
200 -900
5
3 7 100
-5 2 -1000
1 -1 50
2 -9 -3000
7 1 -400

Expected output