首页 > ACM题库 > HDU-杭电 > HDU 4798-Skycity-分治-[解题报告]HOJ
2015
09-18

HDU 4798-Skycity-分治-[解题报告]HOJ

Skycity

问题描述 :

The world’s new tallest building is going to be built in Changsha, which will be called as "Skycity". The Skycity is going to be built as a circular truncated cone, radius of its bottom is marked as R, and radius of its top is marked as r, height of the building is marked as H, and there will be F floors with exact the same height in the whole building.
After construction of the building’s skeleton, the construction team is going to construct the curtain wall using thousands of glass panes. The curtain wall is installed in each floor. When installing the curtain wall in a floor, first the construction team will measure the radius r’ of the ceiling, then they will install the glass curtain wall as a regular prism which can exactly contain the ceiling circle. When constructing the glass curtain wall, all the glass pane has a minimum area requirement S, and amount of glass usage should be as little as possible.
Graph Reconstruction

As all the glass has exact the same thickness, so we can calculate the consumption of each glass pane as its area. Could you calculate the minimum total glass consumption?

输入:

There will be multiple test cases. In each test case, there will be 5 integers R, r (10 ≤ r < R ≤ 10000), H (100 ≤ H ≤ 10000), F (10 ≤ F ≤ 1000) and S (1 ≤ S <Graph Reconstruction× r × H ÷ F) in one line.

输出:

There will be multiple test cases. In each test case, there will be 5 integers R, r (10 ≤ r < R ≤ 10000), H (100 ≤ H ≤ 10000), F (10 ≤ F ≤ 1000) and S (1 ≤ S <Graph Reconstruction× r × H ÷ F) in one line.

样例输入:

50 10 800 120 5
300 50 2000 500 10

样例输出:

149968.308
2196020.459

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3733


Skycity



Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge


The world’s new tallest building is going to be built in Changsha, which will be called as "Skycity". The Skycity is going to be built as a circular truncated cone, radius of its bottom is marked as R, and radius of its top is marked as r,
height of the building is marked as H, and there will be F floors with exact the same height in the whole building.

After construction of the building’s skeleton, the construction team is going to construct the curtain wall using thousands of glass panes. The curtain wall is installed in each floor. When installing the curtain wall in a floor, first the construction team
will measure the radius r’ of the ceiling, then they will install the glass curtain wall as a regular prism which can exactly contain the ceiling circle. When constructing the glass curtain wall, all the glass pane has a minimum area requirment S,
and amount of glass usage should be as little as possible.

Skycity

As all the glass has exact the same thickness, so we can calculate the consumption of each glass pane as its area. Could you calculate the minimum total glass consumption?


题意:阅读理解题。。。题目描述很飘逸,再配上这张可怕的图,现场赛的话我肯定是不敢看的,读懂题意后才知道这就一道水题。就是给你一个圆台,底面和顶面半径分别为R,r,然后高度为H,一共F层,每层高度一样,然后要在每层的天花板上贴方格玻璃,方格玻璃要满足以下几个条件:

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

思路:直接用公式算就行,首先每层的天花板半径能够算出来,然后由于每层高度一样,那么每层玻璃的宽度也一样,只要考虑每层的长度就行,对于特定的一层,可以二分多边形的边数来确定玻璃的长度,求出长度每一层玻璃所用面积就好求了。只要搞懂了题意随便水就行了。

代码如下:

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

参考:http://blog.csdn.net/dyx404514/article/details/16961611