Cod sursa(job #563636)

Utilizator DraStiKDragos Oprica DraStiK Data 25 martie 2011 16:55:15
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <algorithm>
#include <vector>
using namespace std;

#define mp make_pair
#define sc second
#define fs first

#define MAX 60005
#define DIM 805

pair <double,double> bnd[DIM][DIM];
pair <int,int> v[DIM];
int v_x[DIM],lg[DIM];
int N,M,P,B,nrt;
bool viz[MAX];

void read ()
{
    int i;

    scanf ("%d%d",&N,&M);
    for (i=1; i<=N; ++i)
    {
        scanf ("%d%d",&v[i].fs,&v[i].sc);
        if (!viz[v[i].fs])
        {
            viz[v[i].fs]=1;
            v_x[++P]=v[i].fs;
        }
    }
    v[N+1]=v[1];
}

void init ()
{
    pair <int,int> p1,p2;
    double tg,y1,y2;
    int i,j,x1,x2;

    sort (v_x+1,v_x+P+1);
    for (i=2; i<=P; ++i)
    {
        x1=v_x[i-1]; x2=v_x[i]; ++B;
        for (j=2; j<=N; ++j)
        {
            p1=v[j-1]; p2=v[j];
            if (p1>p2)
                swap (p1,p2);

            if (p1.fs<=x1 && x2<=p2.fs)
            {
                tg=(double)(p2.sc-p1.sc)/(p2.fs-p1.fs);
                y1=tg*(x1-p1.fs)+p1.sc;
                y2=tg*(x2-p1.fs)+p1.sc;
                bnd[B][++lg[B]]=mp (y1,y2);
            }
        }
        sort (bnd[B]+1,bnd[B]+lg[B]+1);
    }
}

inline int caut_bin (int x)
{
    int st,dr,mij;

    for (st=1, dr=P; st<=dr; )
    {
        mij=(st+dr)>>1;
        if (v_x[mij]<x)
            st=mij+1;
        else
            dr=mij-1;
    }

    return dr;
}

inline int f (double x1,double y1,double x2,double y2,double x3,double y3)
{
    double sgn;

    sgn=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);

    if (sgn<0)
        return -1;
    if (sgn>0)
        return 1;
    return 0;
}

inline int in_polig (int banda,int x,int y)
{
    int st,dr,mij,sol,val;

    sol=0;
    for (st=1, dr=lg[banda]; st<=dr; )
    {
        mij=(st+dr)>>1;
        val=f ((double)x,(double)y,(double)v_x[banda],bnd[banda][mij].fs,(double)v_x[banda+1],bnd[banda][mij].sc);

        if (!val)
            return 1;
        else if (val<0)
            st=mij+1;
        else
        {
            sol=mij;
            dr=mij-1;
        }
    }

    if (!sol || !((lg[banda]-sol+1)&1))
        return 0;

    return 1;
}

void solve ()
{
    int i,x,y,banda;

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

        if (v_x[1]<=x && x<=v_x[P])
        {
            banda=caut_bin (x);
            if (!banda)
                ++banda;

            if (in_polig (banda,x,y))
                ++nrt;
            else if (++banda<=B && x==v_x[banda])
                if (in_polig (banda,x,y))
                    ++nrt;
        }
    }

    printf ("%d",nrt);
}

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

    read ();
    init ();
    solve ();

    return 0;
}