首页 > 代码库 > hdu 4946 Area of Mushroom

hdu 4946 Area of Mushroom

2024-07-17 19:27:08   219人阅读

题意：

　　在二维平面上，给定n个人

　　每个人的坐标和移动速度v

　　若对于某个点，只有 x 能最先到达（即没有人能比x先到这个点或者同时到这个点）

　　则这个点称作被x占有，若有人能占有无穷大的面积 则输出1 ，否则输出0

 

思路：

　　1、把所有点按速度排个序，然后把不是最大速度的点去掉

　　剩下的点才有可能是占有无穷大的面积

　　2、给速度最大的点做个凸包，则只有在凸包上的点才有可能占有无穷大

　　若一个位置有多个人，则这几个人都是不能占有无穷大的。

　　凸包上边里共线的点是要保留的。

 

#易错点：

     1.凸包边上要保留共线的点，最好采用水平排序（构造凸包前）

　　2.对于去重点，必须在构造完凸包之后。

 

WA：构造凸包之前去重点

#include<stdio.h>#include<algorithm>#include<fstream>#include<string.h>#include<iostream>using namespace std;const int MAX=550;struct point{    int x;    int y;    int v;    int i;}p[MAX],Ini[MAX],res[MAX];int ans[MAX];bool cmp(point A,point B){    if(A.y==B.y)return A.x<B.x;    return A.y<B.y;}bool cmp1(point A,point B){    if(A.v>B.v)return true;    if(A.v==B.v)    {        if(A.x<B.x)return true;        if(A.x==B.x&&A.y<B.y)return true;    }    return false;}int cross(point A,point B,point C){    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);}int Graham(point *p,int n){    //if (n<3)return n;    sort(p,p+n,cmp);    int i;    int top=0;    for(i=0;i<n;i++)    {        while(top>=2&&cross(res[top-2],res[top-1],p[i])<0)            top--;        res[top++]=p[i];    }    int t=top+1;    for(i=n-2;i>=0;i--)    {        while(top>=t&&cross(res[top-2],res[top-1],p[i])<0)            top--;        res[top++]=p[i];    }    /*for(i=0;i<top;i++)        printf("%d %d\n",res[i].x,res[i].y);*/    return top;}int main(){    int n;    int i,j;    //ifstream cin("A.txt");    int __case=0;    while(cin>>n&&n)    {        for(i=0;i<n;i++)        {            cin>>Ini[i].x>>Ini[i].y>>Ini[i].v;            Ini[i].i=i;        }        sort(Ini,Ini+n,cmp1);            //cout<<Ini[i-1].x<<Ini[i-1].y;        int tmp=0;        for(i=0;i<n;i++)        {            if(Ini[0].v==Ini[i].v)tmp++;            else break;        }        point po;        for(i=0,j=0;i<tmp;)        {            po=Ini[i];            if(i<tmp-1&&Ini[i+1].x==Ini[i].x&&Ini[i+1].y==Ini[i].y)            {                while(i<tmp-1&&Ini[i+1].x==Ini[i].x&&Ini[i+1].y==Ini[i].y)                    i++;            }            else            {                p[j++]=po;            }            i++;        }        printf("Case #%d: ",++__case);        int m=Graham(p,j);        memset(ans,0,sizeof(ans));        for(i=0;i<m;i++)        {            //printf("%d %d %d",res[i].x,res[i].y,res[i].v);            if(res[i].v>0)            {                ans[res[i].i]=1;            }        }        for(i=0;i<n;i++)            printf("%d",ans[i]);        printf("\n");    }    return 0;}
View Code

 

AC：

 


联系
我们