#P1203. [HNOI2005]纸片覆盖[废题]

    ID: 211 传统题 2000ms 256MiB 尝试: 41 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-有限候选集缩减暴力枚举直线相交坐标变换射线法难度分类

[HNOI2005]纸片覆盖[废题]

[HNOI2005] 纸片覆盖

题目描述

小付在一张无限大的白纸上画了 nn 条直线,又剪出了一张形状为简单 mm 边形的纸片。

他可以将纸片在平面上任意平移,但不能旋转或翻转。对于每条直线,位于纸片内部或边界上的部分都被视为覆盖;即使直线的一段与纸片的边完全重合,这一段也计入覆盖长度。

设第 ii 条直线被纸片覆盖的总长度为 LiL_i(如果直线与纸片交于多段,则这些线段的长度都要计入)。求纸片经过一次适当的平移后,所有直线被覆盖长度之和的最大值:

L=max⁡∑i=1nLi.L=\max\sum_{i=1}^{n}L_i.

如果两条输入直线重合,它们仍视为两条直线,各自的覆盖长度分别计入总和。

输入格式

第一行包含两个整数 n,mn,m,分别表示直线条数和多边形顶点数。

接下来 nn 行,每行四个实数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示经过不同两点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 的无限长直线。

接下来 mm 行,每行两个实数 x,yx,y,依照顺时针或逆时针顺序给出多边形的顶点。

输出格式

输出一个实数,表示最大覆盖总长度,保留小数点后三位。

样例 #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

数据范围与说明

  • 1≤n≤101\le n\le 10,1≤m≤101\le m\le 10。由于输入对象为简单多边形,实际有效输入满足 m≥3m\ge3。
  • 所有输入坐标均在 [−10000,10000][-10000,10000] 内,至多两位小数。
  • 输入保证表示直线的两个点不同。
  • 多边形保证简单(不自交),顶点按边界顺序给出,任意连续三个顶点不共线。
  • 多边形不要求为凸多边形。

注意: 本题采用绝对误差判定,允许输出与标准答案相差不超过 10−310^{-3}(另含极小的数值容差)。