#2511. 信心题

题目描述

给定一个 N 个顶点的凸多边形，多边形可能有多个点在一条直线上。

给定 M 条直线，对于每条直线，问这条直线将多边形划分成的两个区域中，面积较小的那个区域的面积。

输入格式

第1行包含一个 ** 正整数** N ，表示了多边形顶点数。

接下来 N 行，每行两个绝对值不超过10000的整数 x , y ，按顺时针或者逆时针顺序给出了多边形每个顶点坐标。

第 N +2行包含一个正整数 M ，表示了询问直线的个数。

接下来M行，每行4个绝对值不超过10000的整数 x 1, y 1, x 2, y 2，表示了询问直线过( x 1, y 1), ( x 2, y 2)两点，并保证了( x 1, y 1) ≠ ( x 2, y 2)。 ** 若直线将凸多边形划分成两部分，则输出较小那部分的面积，否则输出** ** 0** ** 。**

输出格式

应包含 M 行，对于每条直线输出对应结果， ** 保留** ** 4** ** 位小数** 。

样例

样例输入

 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.0000  

0.5000  

0.0000  

25.0000  

数据范围与提示

对于100%的数据，有N, M ≤ 50000

保留小数点后6位或以上，SPJ检查精度为小数点后4位