#H1073. Impossible Spell Card

Impossible Spell Card

题目描述

undefined 非常喜欢玩一款叫做弹幕天邪鬼[1]的游戏。在这款游戏中,玩家需要持续躲避 BOSS 发出的弹幕,一旦玩家被弹幕击中就会失败。

undefined 现在正在攻略游戏中第七天的第六个场景。本关的 BOSS 是拥有时停能力的十六夜咲夜[2],她的符卡“时符「Changeling Magic」”攻击方式如下:首先她会开启时停,并在时停期间内在自身周围布置暂时不动的弹幕,然后在时停即将结束时瞬间交换玩家和她的位置,从而使玩家被弹幕包围。

时符「Changeling Magic」

undefined 意识到,在时停结束后,自己的处境将会非常危险,因此他打算计算出在时停解除的一瞬间,有哪些区域是危险的。

我们可以把十六夜咲夜布置的每个子弹都看作二维平面上的一个点。如果某个位置处在任意一个由三个子弹围成的三角形内部或边上,我们就认为这个位置是危险的,而所有危险位置的并集就组成了危险区域。

现在 undefined 已经提前知道了十六夜咲夜将会布置弹幕的位置,他希望求出危险区域的总面积。

数据格式与约定

输入

第一行一个正整数 n(3n106)n(3 \le n \le 10^6),表示子弹的个数。

接下来 nn 行,每行两个整数 xi,yi(108xi,yi108)x_i,y_i(-10^8 \le x_i,y_i \le 10^8),表示每个子弹的坐标。

输出

输出仅包含一行一个小数,表示危险区域的总面积。为避免浮点误差带来的影响,当你的答案与标准答案的绝对或相对误差不超过 10610^{-6} 时将被判定为正确。

样例

4
0 0
1 0
1 1
0 1
1.0
3
0 0
1 0
0 1
0.5

  1. 弹幕天邪鬼 - THBWiki · 专业性的东方Project维基百科 - TBSGroup (thwiki.cc) ↩︎

  2. 十六夜咲夜 - THBWiki · 专业性的东方Project维基百科 - TBSGroup (thwiki.cc) ↩︎