CF1726H.Mainak and the Bleeding Polygon

NOI/NOI+/CTSC

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

题目大意

以逆时针顺序给出笛卡尔平面上 n(4⩽n⩽5000)n (4 \leqslant n \leqslant 5000) 个点 A1,A2,...,AnA_1,A_2,...,A_n 的坐标,从而确定一凸多边形。该凸多边形的性质有如下保证:

  • 所有点的坐标均为整数且 −109⩽x,y⩽109-10^{9} \leqslant x,y \leqslant 10^{9} 。
  • 对于该凸多边形的任意内角 α\alpha ,均有 90∘⩽α<180∘90^{\circ} \leqslant \alpha < 180^{\circ} 。

现从凸多边形的任意两边上分别取出两点,将所有由两点所确定的、长度不超过 11 的弦所经过的凸多边形内部区域标红。求标红区域的面积。

输入格式

第一行输入 nn 。

之后 nn 行每行给出 11 个点的坐标。

输出格式

只输出标红区域的面积,保留 1111 位小数。误差不超过 10−410^{-4} 即视为正确。

输入输出样例

  • 输入#1

    4
    4 5
    4 1
    7 1
    7 5

    输出#1

    1.17809724510
  • 输入#2

    5
    -3 3
    3 1
    4 2
    -1 9
    -2 9

    输出#2

    1.07823651333

输入解题思路,AI测评打分。不知道怎么写?

首页