题目描述

给定一个 $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 \leq 50000$ 。 保留小数点后 $6$ 位或以上，SPJ 检查精度为小数点后 $4$ 位

题目来源

2011福建集训 Jason , Hsiao 提供 SPJ