Cod sursa(job #1156498)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 27 martie 2014 18:44:45
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 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)
{
    int i;
    vector <pair <pair <int,int> , pair <int,int> > > zone;

    for (i=0;i<segs.size();i++)
        if ((segs[i].first.first<=l)&&(segs[i].second.first>=r))
            zone.push_back(segs[i]);

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

bool above(pair <int,int> point, 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;
        }
    }

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

    while (bot<top)
    {
        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 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(make_pair(points[i-1],points[i]));
    segs.push_back(make_pair(points[n-1],points[0]));

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

    zones.push_back(make_pair(make_pair(-inf,points[0].first),hollow));
    for (i=1;i<points.size();i++)
        zones.push_back(make_pair(make_pair(points[i-1].first,points[i].first),analyze(points[i-1].first,points[i].first)));
    zones.push_back(make_pair(make_pair(points[n-1].first,inf),hollow));

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        which=lower_bound(zones.begin(),zones.end(),make_pair(make_pair(x,x),hollow))-zones.begin();
        if ((which!=0)&&(which!=zones.size()))
            k+=inside(x,y,which);
    }
    g<<k;
    return 0;
}