Cod sursa(job #1894804)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 27 februarie 2017 15:55:56
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <bits/stdc++.h>
#define nmax 802
#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];
int X[nmax];
int n, M;
int lg;
int i, j;
int x, y;
int sol;
bool qxSegment(segment a, segment b)
{
    return max(a.A.y, a.B.y) < max(b.A.y, b.B.y);
}
bool intersect(int x1, int x2, int x3, int x4)
{
    if(x1 == x3 && x2 == x4)
        return 1;
    return (x1 > x3 && x1 < x4) || (x2 > x3 && x2 < x4) || (x3 > x1 && x3 < x2) || (x4 > x1 && x4 < x2);
}
void preprocess()
{
    int i, j;
    sort(X + 1, X + n + 1);
    lg = 1;
    for(i = 2; i <= n; i++)
        if(X[i] != X[i - 1])
            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)) || min(P[j].x , P[j + 1].x) == max(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[0].x , P[n].x), max(P[0].x , P[n].x)) || min(P[0].x , P[n].x) == max(P[0].x , P[n].x))
            {
                if(P[0].x < P[n].x)
                    S.Segments.push_back({P[0], P[n]});
                else S.Segments.push_back({P[n], P[0]});
            }
        sort(S.Segments.begin(), S.Segments.end(), qxSegment);
        Stripes.push_back(S);
        S.Segments.clear();
    }
}
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) - (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);
}
int inside(point A)
{
    int pos = getStripePosition(A);
    if(pos == - 1)
        return 0;
    int 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;
    preprocess();
    while(M--)
    {
        fin >> x >> y;
        sol += inside({x, y});
    }
    fout << sol << "\n";
    return 0;
}