345. Revolution
Time limit per test: 0.5
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
During the last parliament elections in Berland two political parties collected the same amount of votes. Now the first party hired you to help them with their plan of a revolution.
During the revolution they want to split the country into two parts. The party is very democratic, so each member has its own separation plan.
The border of Berland can be considered as a convex polygon on the plane. The polygon can have three or more consecutive vertices lay on one line. Each separation plan is represented by the line of the cut.
Your program should calculate the area of the smallest part of the Berland for each separation plan.
Input
The first line of the input contains integer
N (3 ≤
N ≤ 5 · 10
^{4}). Next
N lines contain coordinates
x_{i},
y_{i} of the Berland border in the clockwise or counterclockwise order. The polygon is nondegenerate. The next line contains integer
P (1 ≤
P ≤ 5 · 10
^{4}). Next
P lines contain coordinates
x_{1,j},
y_{1,j},
x_{2,j},
y_{2,j} of two distinct points on the separation line. All coordinates are real and do not exceed 10
^{4} by the absolute value. They are given with no more than 4 significant digits after decimal point.
Output
Print
P lines. Each line should contain the area of the smallest part after separating Berland with the corresponding line. Print value with at least 6 digits after decimal point. Absolute or relative error must be less than 10
^{5}.
Example(s)
sample input

sample output

5
0 0
0 5
0 10
10 10
10 0
4
0 0 10 10
9 10 10 9
10 1 12 11
10 10 0 5

50.000000
0.500000
0.000000
25.000000
