信心题
时间限制：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