信心题

时间限制:10s      空间限制:128MB

题目描述

给定一个N个顶点的凸多边形,多边形可能有多个点在一条直线上。
给定M条直线,对于每条直线,问这条直线将多边形划分成的两个区域中,面积较小的那个区域的面积。
 


输入格式

第1行包含一个正整数N,表示了多边形顶点数。
接下来N行,每行两个绝对值不超过10000的整数x, y,按顺时针或者逆时针顺序给出了多边形每个顶点坐标。
N+2行包含一个正整数M,表示了询问直线的个数。
接下来M行,每行4个绝对值不超过10000的整数x1, y1, x2, y2,表示了询问直线过(x1, y1), (x2, y2)两点,并保证了(x1, y1) ≠ (x2, y2)。若直线将凸多边形划分成两部分,则输出较小那部分的面积,否则输出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位


题目来源

2011福建集训 Jason丶Hsiao 提供SPJ