Cod sursa(job #1140698)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 12 martie 2014 10:30:50
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.04 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>

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

using namespace std;

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

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

struct segment
{
    int a,b,c;
    float midpoint;
}poly[801];

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

bool viz[60001];

int n,m,cnt,t,r;

struct cmp
{
    bool operator () (const division &a, const division &b)
    {
        return a.x1 < b.x1;
    }
};

float yintersect (segment s, int X)
{
    return (float)(-s.a*X - s.c)/s.b;
}

struct cmp2
{
    bool operator () (const segment &s1, const segment &s2)
    {
        return s1.midpoint < s2.midpoint;
    }
};

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

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

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

        int val = d[wh].S[mid].a*q.x + d[wh].S[mid].b*q.y + d[wh].S[mid].c;

        if (val == 0)
            return 1;

        if (val > 0)
            lo = mid;
        else hi = mid;
    }

    if ((lo&1)==0)
        return 1;
    return 0;
}

void bs ()
{
    int lo = 0, hi = t;

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

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

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

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

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

        if (!viz[p[i].x])
        {
            d[++t].x1 = p[i].x;
            viz[p[i].x] = 1;
        }
    }

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

        poly[j].a = p[j].y - p[jj].y;
        poly[j].b = p[jj].x - p[j].x;
        poly[j].c = p[jj].y*p[j].x - p[jj].x*p[j].y;

        if (p[j].x > p[jj].x)
        {
            poly[j].a = -poly[j].a;
            poly[j].b = -poly[j].b;
            poly[j].c = -poly[j].c;
        }
    }

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

    for (int i=1; i<t; ++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;

            point a = p[j], b = p[jj];

            if (a.x > b.x)
                swap (a,b);

            if (det (refa,refb,b) > 0 && det(refa,refb,a) <= 0)
            {
                d[i].S.push_back (poly[j]);

                float y1 = yintersect (poly[j],d[i].x1);
                float y2 = yintersect (poly[j],d[i].x2);

                d[i].S[d[i].S.size()-1].midpoint = (y1+y2)/2;
            }
        }

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

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

        bs ();
    }

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