JYYR 的饼干 biscuit(1S128M)
【问题描述】 JYYR 的 baby 喜欢吃饼干,但 baby 有一个不好的习惯,每次都要蘸着牛奶吃,她总是拿着饼干去蘸牛奶,可以旋转着饼干去蘸牛奶,且尽可能多蘸(即蘸的时候可以让饼干的边靠着瓶底),因为被牛奶侵泡后饼干原先的营养价值被损失,但带进新营养,已 知当(饼干未被侵泡面积-侵泡面积)^2 越小时,营养价值越大。现有深度为 K 的牛奶,请问 JYYR 给baby 提供多深的牛奶,才能使营养价值最大?给定饼干端点(注:饼干为凸多边形)
【输入】
输入包括几组数据,每组数据如下:
第一行两个数 n,k,表示饼干顶点个数和有深度为 k 的牛奶;
接下来 n 行,按逆时针给出每个点坐标,每行两个数 x,y;
输入以文件结束符结束。
【输出】 每组数据一行,一个浮点数表示营养价值最大时提供牛奶深度
输出保留 3 位小数;
【输入输出样例】
In
3 1
0 0
3 0
2 2
out
0.218 【数据范围】
对于 30%的数据 2<n<=5000,k<100;
对于 50%的数据 n<=10000,k<2000;
对于 100%的数据 n<=200000,k<10000,|x|,|y|<10000;