hdu2108[判凸多边形]

发表于 | 分类于 ， ， | 阅读数 次

链接:hdu2108[判凸多边形]

题解

  • 其实这道题只需要O(N)扫一遍就ok,只是为了写个Graham的板子
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<stack>
    #include<algorithm>
    #define rint register int
    #define rep(i,x,y) for(rint i=x;i<=y;++i)
    #define repd(i,x,y) for(rint i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e6+7;
    typedef pair<int,int> s;
    int x[N],y[N],id[N],n,vis[N],res[N],cnt;
    template <typename T>inline void read(T &x){
    	x=0;char c;int sign=1;
    	do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
    	do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
    	x*=sign;
    }
    inline int cmp(int a,int b){return y[a]==y[b]?x[a]<x[b]:y[a]<y[b];}
    inline int det(int x1,int x2,int y1,int y2){return x1*y2-y1*x2;}
    inline int crp(s a,s b,s c){return det(b.first-a.first,c.first-a.first,b.second-a.second,c.second-a.second);}
    inline void init(){rep(i,1,n)read(x[i]),read(y[i]),id[i]=i;sort(id+1,id+n+1,cmp);}
    inline int solve(){
     	rep(i,1,n){
    		while(cnt>1&&crp(s(x[res[cnt-1]],y[res[cnt-1]]),s(x[res[cnt]],y[res[cnt]]),s(x[id[i]],y[id[i]]))<=0)cnt--;
    		res[++cnt]=id[i];
    	}
    	int tmp=cnt;
    	repd(i,n-1,1){
    		while(cnt>tmp&&crp(s(x[res[cnt-1]],y[res[cnt-1]]),s(x[res[cnt]],y[res[cnt]]),s(x[id[i]],y[id[i]]))<=0)cnt--;
    		res[++cnt]=id[i];
    	}
    	return cnt==n+1;
    }
    int main(){
    	while(~scanf("%d",&n)&&n){
    		cnt=0;init();
    		puts(solve()?"convex":"concave");
    	}
    	return 0;
    }