Cod sursa(job #998298)

Utilizator StanAndreiAndrei Stan StanAndrei Data 16 septembrie 2013 18:32:03
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.6 kb
#include <stdio.h>

#define NMAX 805
#define MMAX 60005

struct Punct{double x,y;};

Punct P[NMAX];
Punct PCT[MMAX];

int n,m;

void read()
{
    scanf("%d %d\n",&n,&m);

    int i,a,b;
    for (i=1;i<=m;i++)
    {
        scanf("%d %d\n",&a,&b);
        P[i].x=a;
        P[i].y=b;
    }
    for (i=1;i<=n;i++)
    {
        scanf("%d %d\n",&a,&b);
        PCT[i].x=a;
        PCT[i].y=b;
    }
}

int inside(Punct M)
{
    int i,intersect=0;
    double t,cy;
    P[m+1]=P[1];

    for (i=1;i<=m;i++)
    {
        if ((P[i].x<M.x && M.x<P[i+1].x)||(P[i].x>M.x && M.x>P[i+1].x))
        {
            t=(M.x-P[i+1].x)/(P[i].x-P[i+1].x);
            cy=t*P[i].y+(1-t)*P[i+1].y;
            if (M.y==cy) return 0;
            else
                if (M.y>cy) intersect++;
        }
        if (P[i].x==M.x && P[i].y>=M.y && P[i+1].y<=M.y)
            return 1;
        if (P[i].x==M.x && P[i].y<=M.y)
        {
            if (P[i].y==M.y) return 0;
            if (P[i+1].x==M.x)
            {
                if ((P[i].y<=M.y && M.y<=P[i+1].y) || (P[i].y>=M.y && M.y>=P[i+1].y))
                    return 0;
            }
            else
                if (P[i+1].x>M.x) intersect++;
        }
    }
    if (intersect%2) return 1;
    return 0;
}

void solve()
{
    int nr=0,i;
    for (i=1;i<=n;i++)
        if (inside(PCT[i]))
            nr++;

    printf("%d\n",nr);
}

int main()
{
    freopen ("poligon.in","r",stdin);
    freopen ("poligon.out","w",stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}