Cod sursa(job #549305)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 8 martie 2011 13:27:06
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.17 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

#define eps 1e-3
#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<int> marg[NMAX];
set <int> myset;
set <int> ::iterator it;

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)
{
    if(p.x<vec[1] || p.x>vec[nr])
        return 0;
        
    int st,dr,pfas,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[mij],v[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;
    }

    st=0;dr=marg[pfas].size()-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        c=comp(v[marg[pfas][mij]].y, p.y);
        if(!c)
            return 0;
        else if(c==1)
            dr=mij-1;
        else
        {
            last=mij;
            st=mij+1;
        }
    }
    
    return (last+1)&1;
}

int cmp2(const int& a,const int& b)
{
    return v[a].y<v[b].y;
}

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(xmin<=vec[i] && vec[i+1]<=xmax)
                fas[i].pb(j);
        }
    for(i=1;i<nr;i++)
        sort(fas[i].begin(),fas[i].end(),cmp(i));

    for(i=1;i<=nr;i++)
        for(j=1;j<=n;j++)
            if(vec[i]==v[j].x)
                marg[i].pb(j);
    for(i=1;i<=nr;i++)
        sort(marg[i].begin(),marg[i].end(),cmp2);
        
    for(;m;m--)
    {
        scanf("%d%d",&i,&j);
        sol+=interior(mp(i,j));
    }
    printf("%d\n",sol);
    return 0;
}