luogu#P11441. [Code+#6] 进阶法师

    ID: 35338 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>计算几何Special Judge凸包叉积旋转卡壳

[Code+#6] 进阶法师

题目背景

搬运自 Code+ 第 6 次网络赛

题目描述

传说在 100000100000 年后,又有大量陨石即将撞击企鹅大陆。散布在企鹅大陆各个地点的进阶企鹅法师们张开法阵保护企鹅大陆。

法师站在一些固定的点,如果一个点与某两个法师连线形成的夹角大于等于 9090 度,那么这个点可以免于灾害。

每个法师的坐标可以使用一组非负整数 (X,Y)\left(X, Y\right) 表示。不存在两个法师在同一个位置。

一想到这里,企鹅豆豆又想到一个问题——能被保护的区域的面积有大?

输入格式

输入的第一行包含一个正整数 nn,表示法师人数,保证 2n1052 \le n \le 10^5

接下来 nn 行每行两个非负整数,表示一位法师的坐标位置。保证数值不超过 10910^9

输出格式

输出一个小数,表示被保护的区域的面积。如果你的输出与标算的答案的相对误差不超过 10710^{-7} 即被认为是正确的。

2
0 0
0 2
3.14159265358979326666666666666233333333
3
0 1
3 0
2 2
10.353981582

提示

样例解释

【样例 1】

对于样例一,显然被保护面积是以这两点连线作为直径的圆形。根据圆的面积计算公式即可得出答案。而且你与标算的相对误差不超过 10710^{-7} 即被认为正确。

【样例 3】

见题目目录下的 3.in3.ans

数据范围

保证 2n1052 \le n \le 10^50X,Y1090\le X,Y\le 10^9