Cod sursa(job #1156533)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 27 martie 2014 19:15:55
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.57 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 ((segs[i].first.first==segs[i].second.first)&&((segs[i].first.first==l)||(segs[i].first.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;
}

bool above(pair <int,int> point, pair <pair <int,int> , pair <int,int> > seg)
{
    if (seg.first.first==seg.second.first)
    {
        if (point.second>seg.second.second)
            return 1;
        if (point.second<seg.first.second)
            return -1;
        return 0;
    }

    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]);

    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,i;
    ans=0;
    top=zones[which].second.size()-1;
    bot=0;

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

        if (i==1)
        {
            ans=mid;
            bot=mid+1;
        }

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

        if (i==0)
            return 1;
    }

    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;
}

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])));

    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);

        which=fbs(x);

        //cout<<"\nWHICH? "<<which<<'\n';

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