Cod sursa(job #563710)

Utilizator DraStiKDragos Oprica DraStiK Data 25 martie 2011 19:38:33
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

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

#define INF 60005
#define EPS 1e-9
#define DIM 805

set <pair <int,pair <int,int> > > oz;
vector <int> banda[DIM];
pair <int,int> v[DIM];
int N,M,P,nrt;
int v_x[DIM];
double midx;

void read ()
{
    int i;

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

inline double find_y (int a,double b)
{
    double n,m;

    n=(double)(v[a+1].sc-v[a].sc)/(v[a+1].fs-v[a].fs);
    m=(double)v[a].sc-n*v[a].fs;

    return n*b+m;

}

struct cmp
{
    bool operator () (const int &a,const int &b)
    {
        return find_y (a,midx)<find_y (b,midx);
    }
};

void init ()
{
    int i,j;

    v_x[0]=-1; sort (v_x,v_x+N+1);
    P=unique (v_x,v_x+N+1)-v_x; v_x[P]=INF;

    for (i=1; i<=N; ++i)
    {
        for (j=1; j<=P; ++j)
        {
            if (min (v[i].fs,v[i+1].fs)<=v_x[j-1] && v_x[j]<=max (v[i].fs,v[i+1].fs))
                banda[j].pb (i);
            if (v[i].fs==v[i+1].fs && v[i].fs==v_x[j-1])
                oz.insert (mp (v_x[j-1],mp (min (v[i].sc,v[i+1].sc),max (v[i].sc,v[i+1].sc))));
        }
        oz.insert (mp (v[i].fs,mp (v[i].sc,v[i].sc)));
    }

    for (i=1; i<=P; ++i)
    {
        midx=(double)(v_x[i-1]+v_x[i])/2;
        sort (banda[i].begin (),banda[i].end (),cmp ());
    }
}

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

    sol=-1;
    st=0; dr=(int)banda[nr_banda].size ()-1;

    while (st<=dr)
    {
        mij=(st+dr)>>1;

        if (find_y (banda[nr_banda][mij],x)<=y)
        {
            sol=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }

    if (sol>=0 && fabs (find_y (banda[nr_banda][sol],x)-y)<EPS)
        return 1;
    if (sol+1<=dr && fabs (find_y (banda[nr_banda][sol+1],x)-y)<EPS)
        return 1;

	return !(sol&1);
}

void solve ()
{
    set <pair <int,pair <int,int> > > :: iterator it;
    int i,x,y,nr_banda;

    for (i=1; i<=M; ++i)
    {
        scanf ("%d%d",&x,&y);
        nr_banda=upper_bound (v_x,v_x+P,x)-v_x;

        if (in_polig (nr_banda,x,y))
            ++nrt;
        else if (v_x[nr_banda-1]==x)
        {
            it=oz.upper_bound (mp (x,mp (y,INF)));
            if (it!=oz.begin ())
            {
                --it;
                if (it->fs==x && it->sc.fs<=y && y<=it->sc.sc)
                    ++nrt;
            }
        }
    }

	printf ("%d",nrt);
}

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

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

    return 0;
}