Cod sursa(job #415378)

Utilizator freak93Adrian Budau freak93 Data 11 martie 2010 11:16:51
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define x first
#define y second

using namespace std;

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

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

typedef pair<int,int> point;
typedef pair<point,point> line;

point a[maxn],b[maxn];
pair<vector<line>,int> E[maxn];
vector<line> aux;

int i,j,n,m,x,y,step,band,rez,weird;

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

bool fcomp(line a,line b)
{
    if(a.x<a.y)
        return area(a.x,a.y,b.y)>=0;
    return area(a.y,a.x,b.y)>=0;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y,a[i].x*=2,a[i].y*=2,b[i]=a[i];
    sort(b+1,b+n+1);
    for(i=1;i<=n;++i)
        E[i].y=b[i].x;
    E[0].y=-1;
    E[n+1].y=70000;
    a[0]=a[n];
    for(i=0;i<n;++i)
        for(j=1;j<=n;++j)
            if(a[i].x!=a[i+1].x)
                if((a[i].x<=E[j].y&&a[i+1].x>=E[j+1].y)||(a[i+1].x<=E[j].y&&a[i].x>=E[j+1].y))
                    E[j].x.push_back(make_pair(a[i],a[i+1]));
    for(i=0;i<=n;++i)
        E[i].x.push_back(make_pair(make_pair(-1,-1),make_pair(70000,-1)));

    for(i=1;i<=n;++i)
        sort(E[i].x.begin(),E[i].x.end(),fcomp);
  /*  for(i=1;i<=n;++i)
    {
        g<<"Banda:"<<i<<"\n";
        for(vector<line>::iterator it=E[i].x.begin();it!=E[i].x.end();++it)
            g<<it->x.x<<" "<<it->x.y<<" "<<it->y.x<<" "<<it->y.y<<"\n";
        g<<"\n";
    }*/

    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        x*=2;
        y*=2;
        for(step=1;step<n;step<<=1);
        for(j=0;step;step>>=1)
            if(j+step<=n&&E[j+step].y<=x)
                j+=step;
        band=j;
        if(band==n&&x==E[band].y)
            --band;
        for(step=1;step<E[band].x.size();step<<=1);
        weird=E[band].x.size();
        for(j=0;step;step>>=1)
            if(j+step<E[band].x.size()&&fcomp(E[band].x[j+step],make_pair(make_pair(x,y),make_pair(x,y))))
                j+=step;
        if((j&1)==0)
            if(j<weird&&area(min(E[band].x[j].x,E[band].x[j].y),max(E[band].x[j].x,E[band].x[j].y),make_pair(x,y))==0)
                ++rez;
            else;
        else
            ++rez;
    }

    g<<rez<<"\n";

    f.close();
    g.close();

    return 0;
}