zj d503 第四題：在凸多邊型內或外

poao899    d503. 第四題：在凸多邊型內或外      AC (4ms, 688KB)   2009-10-30 19:23            .


第一題計算幾何>//<


本來是想找寵物雞(離散greedy?)測資範圍翻到的


是說本來以為不會碰zj了結果還是XD

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

#include<stdio.h>
int getint(){
    int g=0,s=1,c=getchar();
    while(c==10||c==32||c==9||c==',')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;
    void get(){
        x=getint();
        y=getint();
    }
}P[50],test;
int cross(point *o,point *p,point *q){
    long long t=((long long)q->x - (long long)o->x)*((long long)p->y - (long long)o->y) - ((long long)q->y - o->y)*((long long)p->x - o->x);
    return t==0?0:t>0?1:-1;
}
int n,dir;
main(){
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++)
            P[i].get();
        test.get();
        dir=cross(P,P+1,&test);
        int i;
        for(i=1;i<n;i++){
            int c=cross(P+i-1,P+i,&test);
            if(c==0){
                puts("IN");
                break;
            }
            if(dir*c<0){
                puts("OUT");
                break;
            }
        }
        if(i==n)puts("IN");
    }
}