Cod sursa(job #1197092)

Utilizator apopeid15Apopei Daniel apopeid15 Data 10 iunie 2014 19:35:15
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 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";
}