Cod sursa(job #563291)

Utilizator DraStiKDragos Oprica DraStiK Data 24 martie 2011 21:23:57
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 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)
{
    long long deter;
    int st,dr,mij;

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

    if (det (mp (tmp[band-1],bnd[band][st].fs),mp (tmp[band],bnd[band][st].sc),mp (x,y))<0)
        return 0;

    if (det (mp (tmp[band-1],bnd[band][dr].fs),mp (tmp[band],bnd[band][dr].sc),mp (x,y))>0)
        return 0;

    while (dr-st>1)
    {
        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;
        else
            dr=mij;
    }

    return !(st&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]==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);
}

void print ()
{
    vector <pair <int,int> > :: iterator it;
    int i;

    for (i=1; i<=P; ++i)
    {
        printf ("Banda intre %d si %d:\n",tmp[i-1],tmp[i]);
        for (it=bnd[i].begin (); it!=bnd[i].end (); ++it)
            printf ("%d - %d si %d - %d\n",tmp[i-1],it->fs,tmp[i],it->sc);

        printf ("\n\n");
    }
}

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

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

    return 0;
}