#P2903. 多边形

    ID: 2010 传统题 1000ms 512MiB 尝试: 6 已通过: 3 难度: 8 上传者: 标签>CF2400提高+/省选-DAG 动态规划以值为状态断环成链线段相交射线法鞋带公式一维前缀和坐标变换

多边形

题目描述

给定一个任意简单多边形。nn 个顶点可以选择在任意多对顶点之间连边,要求连出来边不能与原有的边和其他连出来的边严格相交。在连出的边的总长度不超过 mm 的情况下,最大化新图形的面积。

输入格式

每组数据第一行两个整数 n,mn,m。接下来 nn 行,按逆时针顺序给出每个顶点的坐标。当 n=m=0n=m=0 时输入结束。

输出格式

对于每组输入数据输出一行,为一个实数,表示新图形的面积,输出保留一位小数。

5 4
0 0
4 0
4 4
2 2
0 4
0 0
16.0

数据规模与约定

对于 100%100\% 的数据,5≤n≤645\le n\le64,0≤m≤4000\le m\le 400。所有坐标均为不超过 100100 的自然数。数据不超过十组。