Cod sursa(job #575389)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 8 aprilie 2011 11:42:21
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>
#define Nmax 802
#define Mmax 60002

struct punct{ int x,y; } P[Nmax];
int N,M;

inline int check(double x,double y){
    int i,inters=0; double cy,t;

    for(i=1;i<=N;++i){

        if( (P[i].x<x && x<P[i+1].x)  || (P[i].x>x && x>P[i+1].x) ){
            t=(x-P[i+1].x)/(P[i].x-P[i+1].x);
            cy = t*P[i].y + (1-t)*P[i+1].y;

            if( y == cy ) return 1; // pe latura orizontala
            if( y > cy ) inters++;
        }

        if( P[i].x == x ){
            if( P[i].y == y ) return 1;
            if( P[i+1].x == x ){
                if( (P[i].y <=y && y<=P[i+1].y) || ( P[i].y>=y && y>=P[i+1].y ) )
                    return 1; // pe latura verticala
            }
            else{
                if( P[i].y > y ) continue;
                if( (P[i+1].x>x && P[i-1].x<x) || ( P[i+1].x<x && P[i-1].x>x) )
                    inters++;
            }
        }
    }
    return inters;
}

int main(){
    int i,x,y,sol=0;
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;++i)
        scanf("%d%d",&P[i].x,&P[i].y);
    P[0]=P[N];
    P[N+1]=P[1];

    for(i=1;i<=M;++i){
        scanf("%d%d",&x,&y);

        if( check(x,y) & 1 ) sol++;
    }

    printf("%d\n",sol);
    fclose(stdin); fclose(stdout);
    return 0;
}