切换到宽版
  • 4334阅读
  • 0回复

多边形纸片覆盖(Polygon) [复制链接]

上一主题 下一主题
离线wing
 
只看楼主 倒序阅读 0 发表于: 2006-10-23
多边形纸片覆盖(Polygon)
   小Q很喜欢几何,这一次,他遇到一个这样的问题:
小Q在一张白纸上画了n条直线,他剪了一个m边形(简单多边形)的小纸片。他想把这个小纸片放在白纸上,使它盖住的线段的总长度最长。小Q还说,这个多边形纸片不能翻转或旋转,只能平移。而且如果直线的某一段刚好与多边形纸片重合,那么,这条线段算作是被覆盖。你能帮他解决这个问题吗?

[输入]
输入文件第一行有两个数n、m(1<=n,m<=10)。
接下来n行每一行4个实数x1,y1,x2,y2,表示一条过(x1,y1)和(x2,y2)的直线。
接下来的m行按照顺序(顺时针或逆时针)输入多边形的每一个点,每一行两个实数x,y,表示点的坐标。多边形保证不自交,且连续的3点不共线。
所有输入的实数都是在-10000到10000中,且不会超过2位小数。

[输出]
   仅一个数,表示最大长度,精确到小数点后3位。

[输入样例]
3 5
6 1 2 5
1 2 8 4
4 -1 5 6
1 0
5 -1
4 2
7 3
4 4

[输出样例]
11.933
快速回复
限100 字节
 
上一个 下一个