[数据结构与算法]题目 1111: Cylinder

题目

Using a sheet of paper and scissors, you can cut out two faces to form a cylinder in the following way:

Cut the paper horizontally (parallel to the shorter side) to get two rectangular parts.

From the first part, cut out a circle of maximum radius. The circle will form the bottom of the cylinder.

Roll the second part up in such a way that it has a perimeter of equal length with the circle’s circumference, and attach one end of the roll to the circle. Note that the roll may have some overlapping parts in order to get the required length of the perimeter.

Given the dimensions of the sheet of paper, can you calculate the biggest possible volume of a cylinder which can be constructed using the procedure described above?

输入
The input consists of several test cases. Each test case consists of two numbers w and h (1 ≤ w ≤ h ≤ 100), which indicate the width and height of the sheet of paper.

The last test case is followed by a line containing two zeros.

输出
For each test case, print one line with the biggest possible volume of the cylinder. Round this number to 3 places after the decimal point.

样例输入

10 10
10 50
10 30
0 0

样例输出

54.247
785.398
412.095

解题思路

根据题目，只可按照平行于宽的方向将纸片剪开，圆在一个纸片上，圆柱体的侧面的矩形在另一个纸片上。有以下两种剪法：

我们知道，圆柱体的体积公式是V = S*H (其中，S是底面圆的面积，S=r²*pi)，因此：

1. 对于剪法一（图左侧方法）而言，V = H*r*r*pi，H为定值w（给定的矩形纸片的宽），因此，要求V最大值，需要r尽可能大。r的约束有两个：一是在宽上2*r <= w；二是在长 (h) 方向上，圆柱体侧面能够围住底面的圆，即(2*r+2*pi*r) <= h。综上，取满足约束的最大的r即可；
2. 对于剪法一（图左侧方法）而言，仍有V = H*r*r*pi，但H为变量，为了求V的最大值，同样H要尽可能大，因此，有H = h-2*r，代入体积公式得到关于r的三次方程，经求导后发现V的变化规律为减-增-减，因此在增-减的转折点r = h/3处取得V最大值；又考虑到在宽方向上r需要满足r = w/2、圆柱体侧面能够围住底面的圆2*pi*r <= w。综上，取满足约束条件下最接近h/3的值。
3. 最后将两种剪法的体积大小比较，取较大的输出即可。

易错点

这应该算个坑了吧~~pi需要取3.1415926535898，一开始取了3.1415926，发现一些测试用例第三位总会相差0.001。

代码

#include<stdio.h>
#define pi 3.1415926535898

double max(double a, double b){
    return a>b ? a:b;
}

double min(double a, double b){
    return a<b ? a:b;
}

int main()
{
	double w,h;//宽，长，1 ≤ w ≤ h ≤ 100
	scanf("%lf %lf",&w,&h);
	double maxr,mr,r,V1,V2;
	while (w!=0 && h!=0)
	{
	    //宽为底边周长，长上取高
	    maxr = w/pi/2;//实际允许取到的r最大值
    	mr = h/3;//数学上的理论体积最大时，r的取值
	    r = min(min(maxr,mr),w/2);
	    V1 = r*r*pi*(h-2*r);
	    
	    //长上取底边周长，宽为高
	    maxr = h/(2*pi+2);//周长对半径的限制
	    mr = w/2;//宽对最大半径的限制
	    r = min(maxr,mr);
	    V2 = r*r*pi*w;
	    
	    printf("%.3lf\n",max(V1,V2));
	    scanf("%lf %lf",&w,&h);
	}
	return 0;
}