acmsguru |
---|
Finished |
129. Inheritance time limit per test: 0.25 sec.
The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
Input The first line contains an integer N (3<=N<=400) - the number of vertexes of the polygon boundaring the territory of King's middle son. Each i-th line of the next N lines contains pair of integers xi, yi (0<=xi,yi<=30000) - a position of the i-th vertex (3<=i<=400). The vertexes are given in random order. There are no any three vertexes laying on a straight line. The next line includes the only integer M (2<=M<=1000) - the number of mineral deposits in the Kingdom. Each j-th line of the next M lines contains two pairs of integers aj1, bj1 - point of the beginning and aj2, bj2 - point of the end of the j-th mineral deposit (0<=aj1,bj1,aj2,bj2<=30000, for 1<=j<=M). The numbers in each line are divided by spaces.
Output Output file should contain M lines. Each j-th line should contain a real number Lj calculated with precision 0.01 - the lehgth of the middle son's part of j-th mineral deposit.
Sample Input 3 1 1 6 1 1 6 4 1 2 1 4 2 2 2 4 4 2 4 4 6 2 6 4
Sample Output 0 2 1 0 | ||||||
|
Name |
---|