SGU 412 — Expedition（探险）

• 来源：SGU 412
• 时间限制：3 秒
• 内存限制：65536 KB
• 输入：标准输入
• 输出：标准输出

题目描述

夏天到了！Peter 已经期待它很久了。这并不奇怪——Peter 即将参加他的第一次地质考察。

你知道考察中最重要的东西是什么吗？当然是一顶大帐篷。

Peter 注意到，从正上方观察时，搭好的帐篷可以看成一个具有 $N$ 个顶点的凸多边形。

当然，只带帐篷还不够。Peter 还需要携带许多其他装备。大家决定把所有装备放在帐篷内部的 $M$ 个架子上。每个架子都可以认为是无限窄的，因此在帐篷的平面示意图上，可以用一条线段表示一个架子。由于架子的摆放方式不同，对应的线段之间可以互相接触，也可以互相相交。

Peter 还在帐篷中央放置了一盏灯。在平面示意图中，这盏灯的位置为 $(0,0)$。

Peter 发现，这些架子会挡住灯光，因此帐篷墙壁的一部分会处于阴影之中。他突然想起，自己的靴子就放在某处墙边。为了判断找到靴子会有多困难，Peter 想知道：

帐篷墙壁上所有处于阴影中的部分，其总长度是多少？

请你帮助他计算这个值。

输入格式

第一行包含两个整数 $N$ 和 $M$：

$$3\le N\le 100000,$$ $$0\le M\le 100000.$$

其中：

• $N$ 表示代表帐篷的凸多边形的顶点数；
• $M$ 表示架子的数量。

接下来 $N$ 行，每行包含两个整数 $x_i,y_i$，表示凸多边形第 $i$ 个顶点的坐标。

所有顶点按照逆时针顺序给出。

随后 $M$ 行，每行包含四个整数：

x_1 y_1 x_2 y_2

表示一个架子在线段示意图中的两个端点 $(x_1,y_1)$ 和 $(x_2,y_2)$。

输入中的所有坐标绝对值均不超过 $10^6$。

保证：

• 点 $(0,0)$ 严格位于凸多边形内部；
• 每一条表示架子的线段都严格位于凸多边形内部；
• 没有任何架子线段经过点 $(0,0)$；
• 不同架子对应的线段可以接触或相交。

输出格式

输出帐篷墙壁上所有阴影部分的总长度。

答案应以实数形式输出，并且小数点后至少输出 6 位数字。可以输出更多位小数。

对于本 OJ，若你的输出值为 $x$，标准答案为 $y$，满足

$$|x-y|\le 10^{-6},$$

则认为答案正确。

因此，不要求与标准答案的小数位数完全一致，也不要求恰好输出 6 位小数。为尽量避免浮点舍入造成的误差，建议输出小数点后 10 位或更多。

例如，当真实答案为 $12$ 时，下面的输出都是格式上允许的：

12.000000

12.0000000000

样例 1

输入

3 1
0 2
-2 -1
3 -3
-1 -1 1 -1

输出

4.615855548972

示意图

样例 2

输入

4 3
-2 -2
2 -2
2 2
-2 2
-1 0 0 -1
1 -1 1 1
-1 1 1 1

输出

12.000000

示意图

说明

架子会遮挡从原点 $(0,0)$ 发出的光线。若帐篷边界上的某一点与原点之间的线段被至少一个架子阻挡，那么该点处于阴影之中。

需要计算凸多边形边界上所有这类阴影区间的长度总和。