Time Limit: 3000/1000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 5059 Accepted
Submission(s): 2294
用向量积来做,当出现向量积时证明有凹角。
向量a * 向量b = (a.x*b.y)-(b.x*a.y);
1 //0MS 228K 635 B C++ 2 #include<stdio.h> 3 #define N 1005 4 struct node{ 5 int x,y; 6 }p[N]; 7 int fun(node a,node b,node c) 8 { 9 return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y); 10 } 11 int main(void) 12 { 13 int n; 14 while(scanf("%d",&n)!=EOF && n) 15 { 16 for(int i=0;i<n;i++) 17 scanf("%d%d",&p[i].x,&p[i].y); 18 if(n<3){ 19 puts("concave");continue; 20 } 21 int flag=1; 22 for(int i=0;i<n;i++) 23 if(fun(p[i],p[(i+1)%n],p[(i+2)%n])<0){ 24 flag=0; 25 break; 26 } 27 if(flag) puts("convex"); 28 else puts("concave"); 29 } 30 return 0; 31 }
hdu 2108 Shape of HDU (数学),布布扣,bubuko.com
原文:http://www.cnblogs.com/GO-NO-1/p/3758440.html