Cod sursa(job #563321)

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

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

#define DIM 805


vector <pair <int,int> > bnd[DIM];
pair <int,int> v[DIM];
vector <int> tmp;
int N,M,P,nrt;

void read ()
{
    int i;

    scanf ("%d%d",&N,&M);
    for (i=1; i<=N; ++i)
    {
        scanf ("%d%d",&v[i].fs,&v[i].sc);
        tmp.pb (v[i].fs);
    }
    v[N+1]=v[1];
}

struct cmp
{
    bool operator () (const pair <int,int> &a,const pair <int,int> &b)
    {
        return a.fs+a.sc<b.fs+b.sc;
    }
};

void init ()
{
    vector <int> :: iterator it;
    pair <int,int> p1,p2;
    int i,x1,x2;

    sort (tmp.begin (),tmp.end ());
    tmp.erase (unique (tmp.begin (),tmp.end ()),tmp.end ());

    it=tmp.begin ();
    if (it!=tmp.end ())
    {
        x1=*it;
        for (++it; it!=tmp.end (); ++it)
        {
            ++P; x2=*it;
            for (i=2; i<=N+1; ++i)
            {
                p1=v[i-1]; p2=v[i];
                if (p1>p2)
                    swap (p1,p2);

                if (p1.fs<=x1 && x2<=p2.fs)
                    bnd[P].pb (mp (p1.sc,p2.sc));
            }

            sort (bnd[P].begin (),bnd[P].end (),cmp ());
            x1=x2;
        }
    }
}

inline long long det (pair <int,int> a,pair <int,int> b,pair <int,int> c)
{
    return 1LL*(b.fs-a.fs)*(c.sc-a.sc)-1LL*(c.fs-a.fs)*(b.sc-a.sc);
}

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

    st=0; dr=(int)bnd[band].size ()-1; sol=-1;

    while (st<=dr)
    {
        mij=(st+dr)>>1;
        deter=det (mp (tmp[band-1],bnd[band][mij].fs),mp (tmp[band],bnd[band][mij].sc),mp (x,y));

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

    }

    if (sol<0 || !(((int)bnd[band].size ()-sol)&1))
        return 0;

    return 1;
}

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

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

        if (x<tmp.front () || x>tmp.back ())
            continue;

        band=upper_bound (tmp.begin (),tmp.end (),x)-tmp.begin ();
        if (tmp[band-1]==x)
        {
            --band;
            if (in_polig (band,x,y))
                ++nrt;
            else if (++band<(int)tmp.size ())
                if (in_polig (band,x,y))
                    ++nrt;
        }
        else 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;
}