Cod sursa(job #563339)

Utilizator DraStiKDragos Oprica DraStiK Data 24 martie 2011 22:42:57
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#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 tmp[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;
            tmp[++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 (tmp+1,tmp+P+1);

    for (i=2; i<=P; ++i)
    {
        ++B; x1=tmp[i-1]; x2=tmp[i];
        for (j=1; j<=N; ++j)
        {
            p1=v[j]; p2=v[j+1];
            if (p2<p1)
                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;

                ++lg[B];
                bnd[B][lg[B]]=mp (y1,y2);
            }
        }
        sort (bnd[B]+1,bnd[B]+lg[B]+1);
    }
}

inline int caut_bin (int val)
{
    int st,dr,mij,sol;

    sol=0;
    for (st=1, dr=B; st<=dr; )
    {
        mij=(st+dr)>>1;

        if (val>tmp[mij])
            st=mij+1;
        else
        {
            sol=mij;
            dr=mij-1;
        }
    }

    return sol;
}

inline int check (int x, int y,int x1,double y1,int x2,double y2)
{
    double sgn;

    sgn=(double)(x1-x)*(y2-y)-(double)(x2-x)*(y1-y);

    if (sgn<0)
        return -1;

    if (sgn>0)
        return 1;

    return 0;
}

inline int in_polig (int band,int x,int y)
{
    int st,dr,mij,sol,f;

    sol=0;
    for (st=1, dr=lg[band]; st<=dr; )
    {
        mij=(st+dr)>>1;
        f=check (x,y,tmp[band],bnd[band][mij].fs,tmp[band+1],bnd[band][mij].sc);

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

    if (sol && (lg[band]-sol+1)&1)
        return 1;

    return 0;
}

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

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

        if (x<tmp[1] || tmp[P]<x)
            continue ;

        band=caut_bin (x);
        if (band>1)
            --band;

        if (in_polig (band,x,y))
            ++nrt;
        else if (band+1<=B && x==tmp[band+1])
            if (in_polig (++band,x,y))
                ++nrt;
    }

    printf ("%d",nrt);
}


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

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

    return 0;
}