Cod sursa(job #560173)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 martie 2011 12:53:39
Problema Poligon Scor 70
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.87 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

#define eps 1e-9
#define mp make_pair
#define minim(a,b) ((a < b) ? a : b)
#define maxim(a,b) ((a > b) ? a : b)
#define pb push_back
#define pi pair<int,int>
#define x first
#define y second
#define NMAX 812

int n,m,nr,vec[NMAX],sol;
pi v[NMAX];
vector<int> fas[NMAX];
vector<double> marg[NMAX];
set <int> myset;
set <int> ::iterator it;
vector< pi > vert[NMAX];
set <int> point[NMAX];

int comp(double a,double b)
{
    if(a+eps>b)
        return 1;
    if(b+eps>a)
        return -1;
    return 0;
}

double yinter(pi p1,pi p2,double xx)
{
    int a=p2.y-p1.y;
    int b=p1.x-p2.x;
    int c=(p1.y*p2.x)-(p2.y*p1.x);
    return ((double)-c-a*xx)/b;
}

class cmp {
private:
    int ind;

public:
    cmp(int i)
    { ind=i; }

    bool operator()(const int& a,const int& b)
    {
        double xmij=(vec[ind]+vec[ind+1])/2.;
        return yinter(v[a],v[a+1],xmij)<yinter(v[b],v[b+1],xmij);
    }

};

int interior(pi p)
{
    int i;
    if(p.x<vec[1] || p.x>vec[nr])
        return 0;
        
    int st,dr,pfas=0,mij,last=-1,c;
    st=1;dr=nr;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(vec[mij]>p.x)
            dr=mij-1;
        else
        {
            pfas=mij;
            st=mij+1;
        }
    }
    if (pfas<nr && vec[pfas]<p.x)
    {
        double r;
        st=0;
        dr=fas[pfas].size()-1;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            r=yinter(v[fas[pfas][mij]],v[fas[pfas][mij]+1],p.x);
            c=comp(r,p.y);
            if(!c)
                return 1;
            if(c==1)
                dr=mij-1;
            else
            {
                last=mij;
                st=mij+1;
            }
        }        
        return (last+1)&1;
    }

    if(point[pfas].find(p.y)!=point[pfas].end())
        return 1;
    int lim=vert[pfas].size();
    for(i=0;i<lim;i++)
        if(vert[pfas][i].x<=p.y && p.y<=vert[pfas][i].y)
            return 1;

    st=0;dr=marg[pfas].size()-1;
//    for(int i=0;i<(int)marg[pfas].size();++i)
//        printf("%.2lf\n", marg[pfas][i]);
    while(st<=dr)
    {
        mij=(st+dr)/2;
        c=comp(marg[pfas][mij], p.y);
        if(!c)
            return 0;
        else if(c==1)
            dr=mij-1;
        else
        {
            last=mij;
            st=mij+1;
        }
    }
    
    return (last+1)&1;
}

int main ()
{
    int i,j,xmin,xmax;
    
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        myset.insert(v[i].x);
    }
    v[n+1]=v[1];
    for(it=myset.begin();it!=myset.end();it++)
        vec[++nr]=*it;
    for(i=1;i<=nr;i++)
        for(j=1;j<=n;j++)
        {
            xmin=minim(v[j].x,v[j+1].x);
            xmax=maxim(v[j].x,v[j+1].x);
            if(i<nr && xmin<=vec[i] && vec[i+1]<=xmax)
                fas[i].pb(j);

            if(xmin<vec[i] && vec[i]<=xmax)
                marg[i].pb(yinter(v[j],v[j+1],vec[i]));
            if(xmin==vec[i] && vec[i]<xmax)
                point[i].insert(v[j].y);
            if(xmin==vec[i] && xmax==vec[i])
            {
                if (v[j].y <= v[j+1].y)
                    vert[i].pb(mp(v[j].y,v[j+1].y));
                else
                    vert[i].pb(mp(v[j+1].y,v[j].y));
            }
        }
    for(i=1;i<nr;i++)
        sort(fas[i].begin(),fas[i].end(),cmp(i));

    for(i=1;i<=nr;i++)
        sort(marg[i].begin(),marg[i].end());

    int t;
    for(t=1;t<=m;t++)
    {
        scanf("%d%d",&i,&j);
        sol+=interior(mp(i,j));
        // if (interior(mp(i,j)))
        //       printf("%d\n",t);
    }
    printf("%d\n",sol);
    return 0;
}