#P1203. [HNOI2005]纸片覆盖[废题]
[HNOI2005]纸片覆盖[废题]
[HNOI2005] 纸片覆盖
题目描述
小付在一张无限大的白纸上画了 条直线,又剪出了一张形状为简单 边形的纸片。
他可以将纸片在平面上任意平移,但不能旋转或翻转。对于每条直线,位于纸片内部或边界上的部分都被视为覆盖;即使直线的一段与纸片的边完全重合,这一段也计入覆盖长度。
设第 条直线被纸片覆盖的总长度为 (如果直线与纸片交于多段,则这些线段的长度都要计入)。求纸片经过一次适当的平移后,所有直线被覆盖长度之和的最大值:
如果两条输入直线重合,它们仍视为两条直线,各自的覆盖长度分别计入总和。
输入格式
第一行包含两个整数 ,分别表示直线条数和多边形顶点数。
接下来 行,每行四个实数 ,表示经过不同两点 和 的无限长直线。
接下来 行,每行两个实数 ,依照顺时针或逆时针顺序给出多边形的顶点。
输出格式
输出一个实数,表示最大覆盖总长度,保留小数点后三位。
样例 #1
样例输入 #1
3 5
6 1 2 5
1 2 8 4
4 -1 5 6
1 0
5 -1
4 2
7 3
4 4
样例输出 #1
11.933
数据范围与说明
- ,。由于输入对象为简单多边形,实际有效输入满足 。
- 所有输入坐标均在 内,至多两位小数。
- 输入保证表示直线的两个点不同。
- 多边形保证简单(不自交),顶点按边界顺序给出,任意连续三个顶点不共线。
- 多边形不要求为凸多边形。
注意: 本题采用绝对误差判定,允许输出与标准答案相差不超过 (另含极小的数值容差)。