Cod sursa(job #1202981)

Utilizator andreiiiiPopa Andrei andreiiii Data 30 iunie 2014 13:14:03
Problema Poligon Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.81 kb
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int Nmax = 805, INF = 0x3f3f3f3f;

class Point {
public:
    int x, y;

    Point(const int _x = 0, const int _y = 0):
        x(_x),
        y(_y) {}

    bool operator < (const Point &e) const {
        if (x != e.x) return x < e.x;
        return y < e.y;
    }
};

class Segment {
public:
    Point a, b;

    Segment(const Point _a = Point(0, 0), const Point _b = Point(0, 0)):
        a(_a),
        b(_b) {}

    bool operator < (const Segment &e) const {
        return a.x < e.a.x;
    }

    bool isVertical() const {
        return a.x == b.x;
    }

    void swap() {
        Point aux = a;
        a = b;
        b = aux;
    }
};

Point Points[Nmax];
Segment Segments[Nmax];
vector<int> BSegments[Nmax], VerticalSegments[Nmax];

long long Det(const Point o, const Point a, const Point b)
{
    return 1LL * (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}


struct comp {
    bool operator()(const int &a, const int &b) const {
        return (Det(Segments[a].a, Segments[b].b, Segments[b].a) >= 0 && Det(Segments[a].b, Segments[b].b, Segments[b].a) >= 0);
    }
};

int main()
{
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);

    int N, Q;
    scanf("%d%d", &N, &Q);

    vector<int> Xs(1, -INF);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d%d", &Points[i].x, &Points[i].y);
        Xs.push_back(Points[i].x);
    }

    for (int i = 1; i < N; i++)
        Segments[i] = Segment(Points[i], Points[i + 1]);
    Segments[N] = Segment(Points[N], Points[1]);

    for (int i = 1; i <= N; i++)
        if (Segments[i].a.x > Segments[i].b.x)
            Segments[i].swap();
        else if (Segments[i].isVertical() && Segments[i].a.y > Segments[i].b.y)
            Segments[i].swap();

    sort(Xs.begin(), Xs.end());
    Xs.erase(unique(Xs.begin(), Xs.end()), Xs.end());

    for (int i = 1; i < int(Xs.size()); i++)
    {
        BSegments[i].push_back(0);
        VerticalSegments[i].push_back(0);
        for (int j = 1; j <= N; j++)
        {
            if (Segments[j].isVertical() && Segments[j].a.x == Xs[i])
            {
                VerticalSegments[i].push_back(j);
                continue;
            }

            if (Segments[j].a.x <= Xs[i - 1] && Xs[i] <= Segments[j].b.x)
                BSegments[i].push_back(j);
        }
        sort(BSegments[i].begin() + 1, BSegments[i].end(), comp());
        sort(VerticalSegments[i].begin() + 1, VerticalSegments[i].end());
    }

    int Sol = 0;
    while (Q--)
    {
        Point P;
        scanf("%d%d", &P.x, &P.y);

        int posx = lower_bound(Xs.begin() + 1, Xs.end(), P.x) - Xs.begin();

        if (posx == int(Xs.size())) continue;

        bool ok = 0;

        if (P.x == Xs[posx])
        {
            int posy = 0;
            for (int step = (1 << 9); step; step >>= 1)
            {
                if ((posy | step) < int(VerticalSegments[posx].size()) && Segments[VerticalSegments[posx][posy | step]].b.y < P.y)
                    posy |= step;
            }
            posy++;

            if (posy < int(VerticalSegments[posx].size()))
            {
                const Segment S = Segments[VerticalSegments[posx][posy]];
                if (S.a.y <= P.y) ok = 1;
            }
        }

        int posy = 0;
        for (int step = (1 << 9); step; step >>= 1)
        {
            if ((posy | step) < int(BSegments[posx].size()) && Det(P, Segments[BSegments[posx][posy | step]].b, Segments[BSegments[posx][posy | step]].a) < 0)
                posy |= step;
        }
        posy++;

        if (posy > 0 && posy < int(BSegments[posx].size()) && !Det(P, Segments[BSegments[posx][posy]].b, Segments[BSegments[posx][posy]].a))
            ok = 1;
        else
            ok |= ((posy & 1) ^ 1);

        if (ok) Sol++;
    }

    printf("%d\n", Sol);
}