Cod sursa(job #1895285)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 27 februarie 2017 21:18:13
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 kb
#include <bits/stdc++.h>
#define nmax 802
#define Cmax 60002
#define ll long long
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
struct point
{
    int x, y;
};
struct segment
{
    point A, B;
};
struct stripe
{
    int x1, x2;
    vector <segment> Segments;
};
vector <stripe> Stripes;
point P[nmax];
vector <point>V[Cmax];
int X[nmax];
int n, M;
int lg;
int i, j;
int x, y;
int sol;
bool qxSegment(segment a, segment b)
{
    return min(a.A.y, a.B.y) < min(b.A.y, b.B.y);
}
bool intersect(int x1, int x2, int x3, int x4)
{
    return max(x1, x3) < min(x2, x4);
}
bool qxPoint(point a, point b)
{
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
void preprocess()
{
    int i, j;
    sort(X + 1, X + n + 1);
    int lg = 1;
    for(i = 2; i <= n; i++)
        if(X[i] != X[lg])
        X[++lg] = X[i];
    stripe S;
    for(i = 1; i < lg; i++)
    {
        S.x1 = X[i];
        S.x2 = X[i + 1];
        for(j = 1; j < n; j++)
            if(intersect(X[i], X[i + 1], min(P[j].x , P[j + 1].x), max(P[j].x , P[j + 1].x)) && P[j].x != P[j + 1].x)
            {
                if(P[j].x < P[j + 1].x)
                    S.Segments.push_back({P[j], P[j + 1]});
                else S.Segments.push_back({P[j + 1], P[j]});
            }
            if(intersect(X[i], X[i + 1], min(P[1].x , P[n].x), max(P[1].x , P[n].x)) && P[1].x != P[n].x)
            {
                if(P[1].x < P[n].x)
                    S.Segments.push_back({P[1], P[n]});
                else S.Segments.push_back({P[n], P[1]});
            }
        sort(S.Segments.begin(), S.Segments.end(), qxSegment);
        Stripes.push_back(S);
        S.Segments.clear();
    }
    for(i = 1; i < n; i++)
        if(P[i].x == P[i + 1].x)
         V[P[i].x].push_back({min(P[i].y, P[i + 1].y), max(P[i].y, P[i + 1].y)});
    if(P[1].x == P[n].x)
         V[P[1].x].push_back({min(P[1].y, P[n].y), max(P[1].y, P[n].y)});
    for(i = 0; i < Cmax - 1; i++)
        sort(V[i].begin(), V[i].end(), qxPoint);
}
int getStripePosition(point A)
{
    int s = 0, d = Stripes.size() - 1, m;
    while(s <= d)
    {
        m = (s + d) / 2;
        if(Stripes[m].x1 <= A.x && Stripes[m].x2 >= A.x)
            return m;
        if(Stripes[m].x1 > A.x)
            d = m - 1;
        else s = m + 1;
    }
    return - 1;

}
ll side(point A, segment S)
{
    return (ll)(A.y - S.A.y) * (S.B.x - S.A.x) - (ll)(A.x - S.A.x) * (S.B.y - S.A.y);
}
bool onSegment(point A, segment S)
{
    return side(A, S) == 0 && (A.x >= S.A.x && A.x <= S.B.x) && (A.y >= min(S.A.y, S.B.y) && A.y <= max(S.A.y, S.B.y));
}
void displayPoint(point A)
{
    cout << A.x << " " << A.y << " ";
}
int inside(point A)
{
    int pos = getStripePosition(A);
    if(pos == - 1)
        return 0;
   // for(i = 0; i < Stripes[pos].Segments.size(); i++)
   //     displayPoint(Stripes[pos].Segments[i].A), displayPoint(Stripes[pos].Segments[i].B), cout << "\n";
    int s = 0, d = V[A.x].size() - 1, m, best = -1;
    while(s <= d)
    {
        m = (s + d) / 2;
        if(V[A.x][m].x >= A.y && A.y <= V[A.x][y].y)
            return 1;
        if(V[A.x][m].x > A.x)
            d = m - 1;
        else s = m + 1;
    }
    s = 0, d = Stripes[pos].Segments.size() - 1, m, best = -1;

    while(s <= d)
    {
        m = (s + d) / 2;
        if(onSegment(A, Stripes[pos].Segments[m]))
            return 1;
        if(side(A, Stripes[pos].Segments[m]) > 0)
        {
            best = m;
            s = m + 1;
        }
        else d = m - 1;
    }
    return (best + 1) % 2;
}
int main()
{
    fin >> n >> M;
    for(i = 1; i <= n; i++)
    {
        fin >> P[i].x >> P[i].y, X[i] = P[i].x;
       // cout << P[i].x << " " << P[i].y << "\n";
    }
    preprocess();
    while(M--)
    {
        fin >> x >> y;
        sol += inside({x, y});

        //cout << x << " " << y << "\n";
       // if(inside({x, y}))
       //     fout << "DA\n";
       // else fout << "NU\n";
    }
    fout << sol << "\n";
    return 0;
}