TIOJ 1178 Convex Hull

poao899    992K    212MS    G++     0.98K     2009-11-11 15:03:21                                    .


知道是按x軸就莫名其妙好co(?


很平凡的凸包(?



//*****************************

//Convex Hull

#include<stdio.h>
#include<algo.h>
int getint(){
    int g=0,c=getchar(),s=1;
    while(c==10||c==32)c=getchar();
    if(c=='-')s=-1,c=getchar();
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g*s;
}
struct point{
    int x,y;
    bool operator<(const point b)const{
        return x==b.x?y<b.y:x<b.x;
    }
    void get(){
        x=getint();
        y=getint();
    }
}P[100000],*stack[200002];
long long cross(point a,point b,point c){
    b.x-=a.x;
    b.y-=a.y;
    c.x-=a.x;
    c.y-=a.y;
    return (long long)b.x*c.y-(long long)b.y*c.x;
}
int top=1,n;
main(){
    n=getint();
    point *q=P;
    for(int i=0;i<n;i++,q++)
        q->get();
    sort(P,q);
    stack[top]=P;
    stack[++top]=P+1;
    for(int i=1;i<n;i++){
        while(top>1 && cross(*stack[top-1],*stack[top],P[i])>=0)
            top--;
        top++;
        stack[top]=&P[i];
    }

    int now=top;
    for(int i=n-2;i>=0;i--){
        while(top>now && cross(*stack[top-1],*stack[top],P[i])>=0)
            top--;
        top++;
        stack[top]=&P[i];
    }
    printf("%d\n",top-1);
}