首页 > 代码库 > hdu2108

hdu2108

2024-07-16 15:44:37   220人阅读

Shape of HDU

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5134    Accepted Submission(s): 2334


Problem Description
话说上回讲到海东集团推选老总的事情，最终的结果是XHD以微弱优势当选，从此以后，“徐队”的称呼逐渐被“徐总”所取代，海东集团（HDU）也算是名副其实了。
创业是需要地盘的，HDU向钱江肉丝高新技术开发区申请一块用地，很快得到了批复，据说这是因为他们公司研发的“海东牌”老鼠药科技含量很高，预期将占全球一半以上的市场。政府划拨的这块用地是一个多边形，为了描述它，我们用逆时针方向的顶点序列来表示，我们很想了解这块地的基本情况，现在请你编程判断HDU的用地是凸多边形还是凹多边形呢？
 

 

Input
输入包含多组测试数据，每组数据占2行，首先一行是一个整数n，表示多边形顶点的个数，然后一行是2×n个整数，表示逆时针顺序的n个顶点的坐标（xi,yi），n为0的时候结束输入。
 

 

Output
对于每个测试实例，如果地块的形状为凸多边形，请输出“convex”,否则输出”concave”，每个实例的输出占一行。
 

 

Sample Input
4
0 0 1 0 1 1 0 1
0
 

 

Sample Output
convex
 
 
这道题和hdu2907题的思路是一样的  ，凸包+简单搜索
 1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 using namespace std; 7 const int N=40; 8 struct point 9 {10     double x,y;11     double angel;12     int id;13 } p[N],stack[N];14 int top,n;15 16 double dis(point a,point b)//求距离17 {18     return sqrt ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));19 }20 21 bool mult(point p1,point p2,point p0)//叉乘22 {23     return (p1.x-p0.x)*(p2.y-p0.y) >= (p2.x-p0.x)*(p1.y-p0.y);24 }25 26 bool cmp(point a,point b)27 {28     if(a.angel == b.angel)29     {30         if (a.x == b.x)31             return a.y > b.y;32         return a.x > b.x;33     }34     return a.angel < b.angel;35 }36 37 void graham()38 {39 //p为点集，n为点的个数，stack为凸包点集，top为凸包个数40     int i,k=0;41     point temp;42     for(i=0; i<n; i++)43         if(p[i].y<p[k].y||((p[i].y==p[k].y)&&(p[i].x<p[k].x)))44             k=i;45     temp=p[0];46     p[0]=p[k];47     p[k]=temp;48     for(i=1; i<n; i++)49         p[i].angel=atan2(p[i].y-p[0].y,p[i].x-p[0].x);50     sort(p+1,p+n,cmp);51     stack[0]=p[0];52     stack[1]=p[1];53     stack[2]=p[2];54     top=3;55     for(i=3; i<n; i++)56     {57         while(top > 2 && mult(stack[top-2],stack[top-1],p[i])<=0)58             top--;59         stack[top++]=p[i];60     }61 }62 int main()63 {64     int i,j,t,pp,q,cnt,ans;65     int flag[500];66     while(scanf("%d",&n)!=EOF&&n)67     {68         cnt=0;69         for(i=0; i<n; i++)70         {71             scanf("%lf%lf",&p[i].x,&p[i].y);72             p[i].id=i;73         }74         graham();75         memset(flag,0,sizeof(flag));76         for(i=0; i<top; i++)77         {78             flag[stack[i].id]=1;79         }80         flag[n]=flag[0];81         for(i=0; i<n; i++)82         {83             if(flag[i]==1&&flag[i+1]==0)84             {85                 cnt++;86                 break;87             }88         }89         if(cnt>0)90             printf("concave\n");91         else92             printf("convex\n");93     }94     return 0;95 }
View Code

 


联系
我们