2013 ACM区域赛长沙 H zoj 3733 (hdu 4798) Skycity

时间:2023-03-09 16:18:40
2013 ACM区域赛长沙 H zoj 3733 (hdu 4798) Skycity

题意:一个圆台,底面和顶面半径分别为R,r,然后高度为H,一共F层,每层高度一样,然后要在每层的天花板上贴方格玻璃,方格玻璃要满足以下几个条件:

方格玻璃面积不能小于S,且方格玻璃要围成一个正多边形,且正好将天花板围住(也就是说天花板的圆面是这个多边形的内接圆),并且要使得贴的玻璃数量尽量少,也就是说这个正多边形的边数要尽量少。问最后所用玻璃的总面积。

思路:先求每个圆的半径,也就是等差数列。再二分正多边行数量。二分容易出错,此题还有精度要求。。。。。

 #include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-);
int R,r,H,t,S;
double h,ans;
double get(int n,double r) {
return 2.0*r*tan(pi/n);
} void binary() {
int limit=;
for(int i=t; i>=; i--) {
double rr=1.0*(R-r)/t*(i-)+r;
int mi=,ma=limit,mid,num;
double s;
while(mi<=ma) {
mid=(mi+ma)>>;
double tmp=get(mid,rr)*h;
if(tmp-S>1e-) {
s=tmp;
num=mid;
mi=mid+;
} else
ma=mid-;
}
ans+=num*s;
limit=num;
}
} int main() {
while(~scanf("%d%d%d%d%d",&R,&r,&H,&t,&S)) {
h=(double)H/t,ans=;
binary();
printf("%.3lf\n",ans);
}
return ;
}