Cod sursa(job #1156581)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 27 martie 2014 19:47:59
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf 2000000000
vector <pair <int,int> > points;
vector <pair <pair <int,int> , pair <int,int> > > segs,hollow;
vector <pair <pair <int,int> , vector <pair< pair <int,int> , pair <int,int> > > > > zones;

bool f(pair <pair <int,int> , pair <int,int> > seg1, pair <pair <int,int> , pair <int,int> > seg2)
{
    int mid1=seg1.first.second+seg1.second.second;
    mid1=mid1/2;
    int mid2=seg2.first.second+seg2.second.second;
    mid2=mid2/2;
    return (mid1<mid2);
}

vector <pair <pair <int,int> , pair <int,int> > > analyze(int l,int r)
{
    //cout<<"ANALYZE:"<<l<<' '<<r<<'\n';
    int i;
    bool b;

    vector <pair <pair <int,int> , pair <int,int> > > zone;

    for (i=0;i<segs.size();i++)
    {
        //cout<<i<<' '<<segs[i].first.first<<' '<<segs[i].first.second<<' '<<segs[i].second.first<<' '<<segs[i].second.second<<' ';
        b=false;
        if ((segs[i].first.first<=l)&&(segs[i].second.first>=r))
            b=true;

        if (b==true)
        {
            //cout<<"IN\n";
            zone.push_back(segs[i]);
        }
        //else
            //cout<<"OUT\n";
    }

    sort(zone.begin(),zone.end(),f);
    return zone;
}

pair <pair <int,int> , pair <int,int> > normalize(pair <pair <int,int> , pair <int,int> > fseg)
{
    pair <pair <int,int> , pair <int,int> > seg;
    if (fseg.first.first==fseg.second.first)
    {
        if (fseg.first.second<fseg.second.second)
            seg=fseg;
        else
        {
            seg.first=fseg.second;
            seg.second=fseg.first;
        }
    }
    else
    {
        if (fseg.first.first<fseg.second.first)
            seg=fseg;
        else
        {
            seg.first=fseg.second;
            seg.second=fseg.first;
        }
    }
    return seg;
}

int above(pair <int,int> point, pair <pair <int,int> , pair <int,int> > seg)
{
    long long m[3][3];
    m[0][0]=seg.first.first;m[0][1]=seg.first.second;m[0][2]=1;
    m[1][0]=point.first;m[1][1]=point.second;m[1][2]=1;
    m[2][0]=seg.second.first;m[2][1]=seg.second.second;m[2][2]=1;

    long long det=m[0][0]*m[1][1]*m[2][2]+m[1][0]*m[2][1]*m[0][2]+m[2][0]*m[0][1]*m[1][2];
    det=det-(m[0][2]*m[1][1]*m[2][0]+m[0][1]*m[1][0]*m[2][2]+m[0][0]*m[1][2]*m[2][1]);

    //cout<<point.first<<' '<<point.second<<"   "<<seg.first.first<<' '<<seg.first.second<<' '<<seg.second.first<<' '<<seg.second.second<<'\n'<<det;
    //cout<<det<<'\n';
    if (det<0)
        return 1;
    if (det>0)
        return -1;
    return 0;
}

int inside(int x,int y,int which)
{
    //cout<<"\nSTART:"<<x<<' '<<y<<' '<<which<<'\n';
    int top,bot,mid,ans,bb;
    ans=0;
    top=zones[which].second.size()-1;
    bot=0;
    //cout<<x<<' '<<y<<' '<<which<<'\n';

    while (bot<=top)
    {
        //cout<<bot<<' '<<top<<'\n';
        mid=(top+bot)/2;
        bb=above(make_pair(x,y),zones[which].second[mid]);
        //cout<<mid<<' '<<bb<<'\n';
        if (bb==1)
        {
            ans=mid+1;
            bot=mid+1;
        }

        if (bb==-1)
            top=mid-1;

        if (bb==0)
            return 1;
    }

    //cout<<ans<<'\n';
    return (ans%2);
}

int fbs(int x)
{
    int top,bot,mid;
    bot=0;top=zones.size()-1;

    while (bot<=top)
    {
        mid=(bot+top)/2;
        if (x>zones[mid].first.second)
            bot=mid+1;
        else
        if (x<zones[mid].first.first)
            top=mid-1;
        else
            return mid;
    }
    return -1;
}

vector < pair <pair <int,int> , pair <int,int> > > vert;

bool onvert(int x,int y)
{
    int which=(upper_bound(vert.begin(),vert.end(),make_pair(make_pair(x,y),make_pair(x,y))))-vert.begin();
    which--;
    if (vert[which].first.first!=x)
        return false;
    if (vert[which].first.second>y)
        return false;
    if (vert[which].second.second<y)
        return false;
    return true;
}

int n,m,i,x,y,which,k;

int main(void)
{
    FILE * f;
    f=fopen("poligon.in","r");
    ofstream g("poligon.out");
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        points.push_back(make_pair(x,y));
    }
    for (i=1;i<points.size();i++)
        segs.push_back(normalize(make_pair(points[i-1],points[i])));

    segs.push_back(normalize(make_pair(points[n-1],points[0])));

    for (i=0;i<segs.size();i++)
        if (segs[i].first.first==segs[i].second.first)
            vert.push_back(segs[i]);

    sort(vert.begin(),vert.end());

    sort(points.begin(),points.end());

    for (i=1;i<points.size();i++)
    {
        if (points[i-1].first!=points[i].first)
            zones.push_back(make_pair(make_pair(points[i-1].first,points[i].first),analyze(points[i-1].first,points[i].first)));
    }

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        if (onvert(x,y))
            k++;
        else
        {
            which=fbs(x);
            //cout<<"\nWHICH? "<<which<<'\n';

            if (which!=-1)
                k+=inside(x,y,which);
        }
    }
    g<<k;
    return 0;
}