Cod sursa(job #1140391)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 11 martie 2014 22:55:43
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>

#define x first
#define y second
#define inf 100000
#define point pair<double,double>

using namespace std;

ifstream fin ("poligon.in");
ofstream fout ("poligon.out");

pair<double,double>p[801],q;

struct segment
{
    double y1,y2;
};

struct division
{
    double x1,x2;
    vector<segment> S;
}d[801];

int n,m,cnt;

bool cmp (division a, division b)
{
    return a.x1 < b.x1;
}

bool cmp2 (segment a, segment b)
{
    if (a.y1 == b.y1)
        return a.y2 < b.y2;
    return a.y1 < b.y1;
}

double det (point a, point b, point c)
{
    return ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y));
}

double yintersect (double X, point a, point b)
{
    double A1,B1,C1,A2,B2,C2;

    A1 = 1;
    B1 = 0;
    C1 = -X;

    A2 = a.y - b.y;
    B2 = b.x - a.x;
    C2 = b.y*a.x - b.x*a.y;

    return (A2*C1 - A1*C2)/(A1*B2 - A2*B1);
}

bool bs2 (int wh, point q)
{
    int lo, hi;

    if (d[wh].x1 == d[wh].x2)
    {
        lo = -1, hi = d[wh].S.size();

        while (hi - lo > 1)
        {
            int mid = (lo + hi)/2;
            if (q.y <= d[wh].S[mid].y1)
                hi = mid;
            else lo = mid;
        }

        if (d[wh].S[hi].y1 == q.y)
            return 1;
        return 0;
    }

    else
    {
        lo = -1, hi = d[wh].S.size();

        while (hi - lo > 1)
        {
            int mid = (lo + hi)/2;

            point a = make_pair (d[wh].x1, d[wh].S[mid].y1), b = make_pair (d[wh].x2, d[wh].S[mid].y2);

            double det1 = det (a,b,q);

            a = make_pair (d[wh].x1,d[wh].S[mid-1].y1), b = make_pair (d[wh].x2, d[wh].S[mid-1].y2);

            double det2 = det (a,b,q);

            if (det1 == 0 || det2 == 0)
                return 1;

            if (det1 > 0 && det2 > 0)
                lo = mid;
            else hi = mid;
        }

        if (lo%2 == 0)
            return 1;
        return 0;
    }
}

void bs (point q)
{
    int lo = 0, hi = n;

    while (hi - lo > 1)
    {
        int mid = (lo + hi)/2;

        if (q.x <= d[mid].x2)
            hi = mid;
        else lo = mid;
    }

    if (bs2 (hi,q))
        ++cnt;
}

int main()
{
    fin>>n>>m;

    for (int i=1; i<=n; ++i)
    {
        fin>>p[i].x>>p[i].y;
        d[i].x1 = p[i].x;
    }

    sort (d+1,d+n+1,cmp);

    for (int i=1; i<n; ++i)
    {
        point refa = make_pair(d[i].x1,inf), refb = make_pair(d[i].x1,-inf);
        d[i].x2 = d[i+1].x1;

        for (int j=1; j<=n; ++j)
        {
            int jj = j+1;
            if (jj == n+1)
                jj = 1;

            if (det (refa,refb,p[jj]) > 0 && det(refa,refb,p[j]) <= 0)
            {
                segment news;

                news.y1 = yintersect (d[i].x1,p[j],p[jj]);
                news.y2 = yintersect (d[i+1].x1,p[j],p[jj]);

                d[i].S.push_back (news);
            }
        }

        sort (d[i].S.begin(),d[i].S.end(),cmp2);
    }

    for (int i=1; i<=m; ++i)
    {
        fin>>q.x>>q.y;

        bs (q);
    }

    fout<<cnt<<"\n";
}