测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A5971. 「SCOI2015」小凸想跑步

编程题 NOI/NOI+/CTSC
知识点

题目描述

小凸晚上喜欢到操场跑步,今天他跑完两圈之后,他玩起了这样一个游戏。

操场是个凸 $ n $ 边形,$ n $ 个顶点按照逆时针从 $ 0 \sim n - 1 $ 编号。现在小凸随机站在操场中的某个位置,标记为 $ P $ 点。将 $ P $ 点与 $ n $ 个顶点各连一条边,形成 $ n $ 个三角形。如果这时 $ P $ 点,$ 0 $ 号点,$ 1 $ 号点形成的三角形的面积是 $ n $ 个三角形中最小的一个,小凸则认为这是一次正确站位。

现在小凸想知道他一次站位正确的概率是多少。

输入格式

第一行包含 $ 1 $ 个整数 $ n $,表示操场的顶点数和游戏的次数。
接下来有 $ n $ 行,每行包含两个整数 $ X_i $、$ Y_i $ 表示顶点的坐标。
输入保证按逆时针顺序输入点,所有点保证构成一个 $ n $ 多边形。所有点保证不存在三点共线。

输出格式

输出一个数,正确站位的概率,保留 $ 4 $ 位小数。

输入输出样例

输入 #1
5
1 8
0 7
0 0
8 0
8 8
输出 #1
0.6316

说明/提示

$ 3 \leq N \leq 10 ^ 5, -10 ^ 9 \leq X, Y \leq 10 ^ 9 $
上一题 去做题 下一题