首页 > ACM题库 > HDU-杭电 > HDU 3847-Trash Removal-计算几何-[解题报告]HOJ
2015
04-13

HDU 3847-Trash Removal-计算几何-[解题报告]HOJ

Trash Removal

问题描述 :

Allied Chute Manufacturers is a company that builds trash chutes. A trash chute is a hollow tube installed in buildings so that trash dropped in at the top will fall down and be collected in the basement. Designing trash chutes is actually highly nontrivial. Depending on what kind of trash people are expected to drop into them, the trash chute needs to have an appropriate size. And since the cost of manufacturing a trash chute is proportional to its size, the company always would like to build a chute that is as small as possible. Choosing the right size can be tough though.

We will consider a 2-dimensional simplification of the chute design problem. A trash chute points straight down and has a constant width. Objects that will be dropped into the trash chute are modeled as polygons. Before an object is dropped into the chute it can be rotated so as to provide an optimal fit. Once dropped, it will travel on a straight path downwards and will not rotate in flight. The following figure shows how an object is first rotated so it fits into the trash chute.

Pyramids

Your task is to compute the smallest chute width that will allow a given polygon to pass through.

输入:

The input contains several test cases. Each test case starts with a line containing an integer n (3 <= n <= 100), the number of points in the polygon that models the trash item.

The next n lines then contain pairs of integers xi and yi (0 <= xi, yi <= 10^4), giving the coordinates of the polygon vertices in order. All points in one test case are guaranteed to be mutually distinct and the polygon sides will never intersect. (Technically, there is one inevitable exception of two neighboring sides sharing their common vertex. Of course, this is not considered an intersection.)

The last test case is followed by a line containing a single zero.

输出:

The input contains several test cases. Each test case starts with a line containing an integer n (3 <= n <= 100), the number of points in the polygon that models the trash item.

The next n lines then contain pairs of integers xi and yi (0 <= xi, yi <= 10^4), giving the coordinates of the polygon vertices in order. All points in one test case are guaranteed to be mutually distinct and the polygon sides will never intersect. (Technically, there is one inevitable exception of two neighboring sides sharing their common vertex. Of course, this is not considered an intersection.)

The last test case is followed by a line containing a single zero.

样例输入:

3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0

样例输出:

Case 1: 2.40
Case 2: 14.15

/*
求出多边形最窄的地段长度
枚举边,求出所有点中到边的距离最大的值
这些值中最小的就是答案
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
const int MAXN = 109;
const double eps = 1e-4;
struct point{
    double x,y;
}p[MAXN],h[MAXN];

inline double distance(const point &p1,const point &p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}//   求两点之间的距离
inline double multiply(const point &sp,const point &ep,const point &op){
      return ((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}//判断sp,ep,op是否满足左转
int cmp(const void *a,const void *b){//按极角排序
    point *p1 = (point *)a;
    point *p2 = (point *)b;
    double t = multiply(*p2,*p1,p[0]);
    if(t>eps) return 1;
    else if(fabs(t)<=eps) 
    {
    if(distance(p[0],*p1)>distance(p[0],*p2)) return 1;
    else return -1;
    }
    else return -1;
}
void anglesort(point p[],int n){//找到最左下方的点
    int i,k=0;
    point temp;
    for(i=1;i<n;i++)
        if(p[i].x<p[k].x ||( fabs(p[i].x-p[k].x)<eps && (p[i].y<p[k].y)))
            k=i;
    temp=p[0],p[0]=p[k],p[k]=temp;
    qsort(p+1,n-1,sizeof(point),cmp);
}
void Graham_scan(point p[],point ch[],int n,int &len){//建立凸包
    int i,top=2;
    anglesort(p,n);
    if(n<3){
        for(i=0,len=n;i<n;i++) ch[i]=p[i];
        return;
    }
    ch[0]=p[0],ch[1]=p[1],ch[2]=p[2];
    p[n]=p[0];
    for(i=3;i<n;i++){
        while(multiply(p[i],ch[top],ch[top-1])>=eps) top--;
        ch[++top]=p[i];
    }
    len=top+1;
}

double judge(point _x,point _y,int len)
{
    double res=0;
    for(int i=0;i<len;i++)
    {
        double tmp=fabs(multiply(h[i],_x,_y))/distance(_x,_y);//面积法求出距离
        if(tmp>res)
        res=tmp;
    }
    return res;
}
double solve(int len)
{
    h[len]=h[0];
    double ans=1<<30;
    for(int i=0;i<len;i++)
    {
        double tmp=judge(h[i],h[i+1],len);//枚举边
        if(tmp<ans)
        ans=tmp;
    }
    return ans;
}
int main(){
    int n,len;
    int d=0;
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y);
        Graham_scan(p,h,n,len);
        printf("Case %d: %.2lf\n",++d,solve(len)+0.005);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wsniyufang/article/details/6705364


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }