Cod sursa(job #417875)

Utilizator mihai0110Bivol Mihai mihai0110 Data 14 martie 2010 23:15:08
Problema Poligon Scor 20
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.2 kb
#include<cstdio>
#define MAXN 801
#define MAXM 60001

int n,m,i,j,x,y,nr,sol;
int lx[MAXN],ly[MAXN];

int semidreapta(int x0, int y0, int x1, int y1, int x2, int y2)
{
    float X;
    int aux;
    X = (float)(x2 - x1) * (y0 - y1) / (y2 - y1) + x1;
    if(y1 > y2)
    {
        aux = y1;
        y1 = y2;
        y2 = aux;
    }
    //printf("x0=%d y0=%d X = %f\n",x0,y0, X);
    if(X == x0 && y0 > y1 && y0 < y2)
        return 1<<30;
    if(X > x0 && y0 > y1 && y0 < y2)
        return 1;
    return 0;
}


int main(void)
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
        scanf("%d%d",&lx[i],&ly[i]);
    lx[++n] = lx[1];
    ly[n] = ly[1];
    for(i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        nr = 0;
        for(j=2;j<=n;j++)
            if((ly[j] == ly[j-1] && ly[j] == y) || (lx[j] == x && ly[j] == y))
            {
                nr = 0;
                break;
            }
            else
                nr+=semidreapta(x,y,lx[j-1],ly[j-1],lx[j],ly[j]);
        if(nr%2 == 1 || nr >= (1<<30))
            sol++;
    }
    printf("%d\n",sol);
    return 0;
}