luogu#P8008. 「Wdsr-3」迷途竹林

    ID: 12004 远端评测题 1000ms 250MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>计算几何Special JudgeO2优化线段相交差分

「Wdsr-3」迷途竹林

题目背景

迷途竹林是生长着高耸入云的、无边无际的竹子的竹林。由于特殊地势的缘故,所有竹子都向着一侧倾斜生长。由于竹子顶部的叶片交错在一起,因此即使竹子的下端已经被砍掉,仍然会因为其他竹子的相互作用而无法掉落。

作为白玉楼的亭师,白玉楼的实际管家,魂魄妖梦时常需要收集一些竹子用于维修竹制家具以及竹楼。因为她拥有精湛的剑术,因此可以在瞬间砍伐一大片的竹子作为材料。当然,妖梦并不希望拥有过多的竹子。因此她会选择一个多边形区域进行采集。在那一瞬间,妖梦会用楼观剑顺着多边形的边进行砍伐。

不过,由于掉落下来的竹子数量实在太多,因此妖梦无暇统计砍下来的竹子。你能帮帮她吗?

题目描述

妖梦在迷途竹林里选定的竹子,可以看作在同一平面上。竹子可以看作有 ++\infty 根,每相邻两根竹子间距相等,并且每根竹子的倾斜程度相同。竹子的高度可以看作是无限高。

妖梦选定了一块多边形区域进行竹子的砍伐。只有在多边形内的部分才会被收集到。多边形共有 nn 条边,为了防止出现歧义,保证任意一条边都不和竹子平行;保证多边形是简单多边形

我们会使用两个实数 θ\thetaaa 来描述这些竹子。这两个字母表示的含义可以参考下图:

现在妖梦需要知道她砍下来的竹子的总长度,也就是求出这些竹子(图中橙色的这些线段)的长度之和。

输入格式

  • 第一行有一个正整数 nn,表示多边形的边数。
  • 接下来 nn 行,将会按照顺时针顺序给出多边形的 nn 个顶点的坐标,第 ii 个点与第 i+1i+1 个点连接 (1i<n)(1\le i<n),第 nn 个点与第 11 个点连接。
  • 接着给出描述线段的参数 θ\thetaaa

输出格式

  • 共一行,一个实数,表示所求得的竹子的总长。你的答案 ans\mathit{ans} 被认为是正确的,当且仅当与标准答案 std\mathit{std} 满足 $\dfrac{|\mathit{ans}-\mathit{std}\ |}{\max(1.0,\mathit{std}\ )}\le 10^{-6}$。
4
2.0000 2.0000
2.0000 -2.0000
-2.0000 -2.0000
-2.0000 2.0000
45.0000 1.0000
22.6274169980
8
0.0000 2.5000
1.0000 1.5000
2.5000 1.0000
2.0000 -1.0000
1.0000 -2.0000
-2.0000 -2.0000
-2.5000 1.0000
-1.0000 2.0000
60.0000 0.8000
23.1662217484

提示

样例 1 解释

容易发现,竹子总长(即橘红色线段的总长度)为 16216\sqrt 2

样例 2 解释

我有一个精妙绝伦的方法解释样例 22,可惜这里空白太小写不下。

数据范围及约定

$$\def{\arraystretch}{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & 10 & \text{A} & 30 \cr\hline 2 & 10^3 & - & 20 \cr\hline 3 & 10^5 & \text{B} & 20 \cr\hline 4 & 10^5 & - & 30 \cr\hline \end{array} $$

特殊性质 A\textbf{A}:保证 θ[80,100);xi,yi10\theta\in[80,100);|x_i|,|y_i|\le 10
特殊性质 B\textbf{B}:保证 θ=90\theta=90

  • 对于 100%100\% 的数据,保证 $3\le n\le 10^5;|x_i|,|y_i|\le 10^4;\theta\in[1,179);\alpha\in[0.1,100]$。输入数据当中出现的浮点数均保留四位小数。