#P1756. [NOI2009] 描边

    ID: 785 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>计算几何高精度2009NOI 系列提交答案Special Judge二分图

[NOI2009] 描边

题目描述

小 Z 是一位杰出的数学家。聪明的他特别喜欢研究一些数学小问题。

有一天,他在一张纸上选择了 nn 个点,并用铅笔将它们两两连接起来,构成 n(n1)2\dfrac{n(n-1)}{2} 条线段。由于铅笔很细,可以认为这些线段的宽度为 00

望着这些线段,小 Z 陷入了冥想中。他认为这些线段中的一部分比较重要,需要进行强调。因此小 Z 拿出了毛笔,将它们重新进行了描边。毛笔画在纸上,会形成一个半径为 rr 的圆。在对一条线段进行描边时,毛笔的中心(即圆心)将从线段的一个端点开始,沿着该线段描向另一个端点。下图即为在一张 44 个点的图中,对其中一条线段进行描边强调后的情况。

现在,小 Z 非常想知道在描边之后纸面上共有多大面积的区域被强调,你能帮助他解答这个问题么?

输入格式

本题是一道提交答案型试题,所有的输入文件 path1.in \sim path10.in 已在相应目录下。

输入文件请点击 这里 下载。

输入文件的第一行为一个正整数 nn,表示选择的点的数目。

第二行至第 n+1n+1 行,其中:第 i+1i+1 行中为两个实数 xi,yix_i,y_i,表示点 ii 的坐标为 (xi,yi)(x_i,y_i)

n+2n+2 行为一个正整数 mm,表示小 Z 认为比较重要的线段的条数。

n+3n+3 行至第 n+m+2n+m+2 行,每行有两个正整数 a,ba,b,表示一条线段。其中 a,ba,b 两个数分别表示该线段的两个端点的编号。

n+m+3n+m+3 行中为一个实数 rr,表示毛笔在纸上形成的圆的半径。

n+m+4n+m+4 行中为四个实数 p1,p2,p3,p4p_1,p_2,p_3,p_4,即评分使用的参数。

输出格式

输出文件 path*.out 仅一行一个数,即为描边后被强调区域的总面积。

2
1 1
1 2
1
1 2
1
0.00001 0.001 0.1 1

5.1415927

提示

每个测试点单独评分。

本题设有 44 个评分参数 p1,p2,p3,p4p_1,p_2,p_3,p_4p1<p2<p3<p4p_1 \lt p_2 \lt p_3 \lt p_4),已在输入文件中给出。

你的得分将按照如下规则给出:

  • 若你的答案与标准答案相差不超过 p1p_1,则该测试点你将得到满分;
  • 否则,若你的答案与标准答案相差不超过 p2p_2,则你将得到该测试点 70%70\% 的分数;
  • 否则,若你的答案与标准答案相差不超过 p3p_3,则你将得到该测试点 40%40\% 的分数;
  • 否则,若你的答案与标准答案相差不超过 p4p_4,则你将得到该测试点 10%10\% 的分数;
  • 否则,该测试点你的得分为 00