HDU 2108 Shape of HDU

题解：按照输入顺序依次将点连接起来，对于连续的三个点p0,p1,p2，令向量a=p1-p0，b=p2-p1

若是凸多边形，那么b相对于a一定是向逆时针方向旋转的

判断两向量的旋转方向，可以使用向量的叉积 a×b＝x1×y2－x2×y1

a×b>0 b在a的逆时针方向
a×b=0 b平行于a（共线）
a×b<0 b在a的顺时针方向

要注意的是，对于最后一个点pn，还要和起始的两个点p0,p1判断一次。

#include <cstdio>

struct node{int x,y;}pt[1010];

int n,x1,x2,y1,y2;

int direction(int x1,int y1,int x2,int y2){return x1*y2-x2*y1;}

int test(){

    int i; pt[n]=pt[0], pt[n+1]=pt[1] ;

    for (i=2;i<=n+1;i++){

        x1=pt[i-1].x-pt[i-2].x,y1=pt[i-1].y-pt[i-2].y;

        x2=pt[i].x-pt[i-1].x,y2=pt[i].y-pt[i-1].y;

        if(direction(x1,y1,x2,y2)<0)return 0;

    }

    return 1;

}

int main (){

    int i;

    while (~scanf("%d",&n)&&n){

        for(i=0;i<n;i++)scanf("%d%d", &pt[i].x, &pt[i].y) ;

        puts(test()?"convex":"concave") ;

    }

    return 0 ;

}

巴特西

HDU 2108 Shape of HDU

最新文章

热门文章