hdu2108 判断是凸多边形还是凹多边形

it2022-05-06  10

题目不难,还是利用向量叉积,看图

接下来,只需按逆时针一次判断一边和一点的关系,若叉积>0,则表示存在大于180的内角,即为凹多边形

#include<iostream> #include<math.h> using namespace std; struct node{ int x,y; }p[100]; int seg(node p1,node p2,node p3) { int d=(p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y); if(d<0) return 1; else return 0; } int main() { int n; while(scanf("%d",&n)==1&&n) { for(int i=0;i<n;i++) scanf("%d %d",&p[i].x,&p[i].y); p[n].x=p[0].x,p[n].y=p[0].y; p[n+1].x=p[1].x,p[n+1].y=p[1].y; int flag=0; if(n<=3) flag=0; else { if(seg(p[0],p[1],p[2])) { for(int i=3;i<n+2;i++) if(!seg(p[i-2],p[i-1],p[i])) { flag=1;break; } else flag=0; } else flag=1; } if(flag) printf("concave\n"); else printf("convex\n"); } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/07/29/2120838.html


最新回复(0)