Cod sursa(job #474122)

Utilizator freak93Adrian Budau freak93 Data 2 august 2010 16:12:53
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cassert>

using namespace std;

const char iname[]="poligon.in";
const char oname[]="poligon.out";
const int maxn=905;
const int maxm=60005;

ifstream f(iname);
ofstream g(oname);

struct point
{
    int x,y;
    point():x(0),y(0){}
    point(int _x,int _y):x(_x),y(_y){}
} a[maxn],ask[maxm];

bool operator<(const point& a,const point &b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

long long area(point a,point b,point c)
{
    return 1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
}

long long area(point a,point b,point c,point d)
{
    return 1LL*a.x*(b.y-d.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(d.y-b.y)+1LL*d.x*(a.y-c.y);
}

int n,i,j,k,m,v[maxn],ans;
vector<int> E[maxn];

bool fcomp(int x,int y)
{
    return area(min(a[x],a[x+1]),max(a[x],a[x+1]),max(a[y+1],a[y]),min(a[y],a[y+1]))>=0;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y,v[i]=a[i].x;
    a[n+1]=a[1];
    v[n+1]=-1;
    v[n+2]=60001;
    sort(v+1,v+n+3);
    k=(unique(v+1,v+n+3)-v)-1;

    for(i=1;i<=n;++i)
        for(j=1;j<k;++j)
            if(min(a[i].x,a[i+1].x)<=v[j]&&max(a[i].x,a[i+1].x)>=v[j+1])
                E[j].push_back(i);

    for(i=1;i<k;++i)
        sort(E[i].begin(),E[i].end(),fcomp),assert(E[i].size()%2==0);

    for(i=1;i<=m;++i)
    {
        f>>ask[i].x>>ask[i].y;
        int step,zone;
        for(step=1;step<k;step<<=1);
        for(j=0;step;step>>=1)
            if(j+step<k&&ask[i].x>=v[j+step])
                j+=step;
        zone=j;
        if(zone==1)
            continue;
        if(v[zone]==ask[i].x&&zone==k-1)
            --zone;
        long long aux;
        for(step=1;step<E[zone].size();step<<=1);
        for(j=0;step;step>>=1)
            if(j+step<=E[zone].size()&&(aux=area(min(a[E[zone][j+step-1]],a[E[zone][j+step-1]+1]),max(a[E[zone][j+step-1]],a[E[zone][j+step-1]+1]),ask[i]))>=0)
            {
                j+=step;
                if(aux==0LL)
                {
                    ++ans;
                    j=0;
                    break;
                }
            }
        if(j==0)
            continue;
        int l=E[zone][j-1];
        if(area(a[l],a[l+1],ask[i])==0LL)
        {
            ++ans;
            continue;
        }
        if(j&1)
            ++ans;
    }

    g<<ans<<"\n";
}