A1-2017级算法上机第一次练习赛 E AlvinZH的儿时梦想——木匠篇

题目描述

AlvinZH儿时有很多梦想,这一次他想成为一个木匠。他的小目标是:先做一个"奇怪"小木桶。他的发小帮他找了一块圆形桶底,出于好心(捣乱),发小还在桶底垂直于同一条直径钉上了不同长度的木条,如图一。你们知道,AlvinZH很懒,他决定在这些木条中选择两根作为基准木条,扔掉其他木条,最后做成形如图二的小木桶(圆柱体/圆柱斜切体,左右粗线即被选择的基准木条)。

简化图如图三,坐标图中,原点为桶底圆心(非小木桶圆心),X轴为对应直径,粗线代表木条,求AlvinZH做的小木桶的最大储水量(木桶不可倾斜)。

要求:必须从圆心两边各选一根木条,圆心处木条可看作属于两边

注意:不要在意怎么做成小木桶的,在意取两根基准木条即可。

输入

输入将由多组测试数据组成,以EOF结尾。

每组数据第一个数为木条数n2≤n≤100)。

接下来n行,每行2个整数xh,表示在坐标轴x位置有一根高度为h的木条(|x|≤100,0h≤100,同一位置至多只有一根木条)。

输出

对于每组数据,输出一行,为木桶的最大储水量(保留三位小数)。

输入样例

2
1 1
-1 1
2
1 2
-1 1

输出样例

3.142
3.142

HINT

水题,O(n)时间,O(n^2)剪枝亦可。

本题容易炸精度,请用PI=acos(-1)

思路

原文地址:https://www.cnblogs.com/zjsyzmx0527/p/10182597.html