Cod sursa(job #1099605)

Utilizator mihai995mihai995 mihai995 Data 5 februarie 2014 23:17:13
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.8 kb
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

template<const int N>
class Poligon{
    struct Point{
        int x, y;

        inline bool operator==(const Point& P) const {
            return x == P.x && y == P.y;
        }
    };

    struct Segm{
        Point A, B;
        Segm() : A(), B() {};
        Segm(Point _A, Point _B){
            if (_A.x > _B.x){
                A = _B;
                B = _A;
            } else {
                A = _A;
                B = _B;
            }
        }

        inline bool operator<(const Segm& S) const {
            if (B.x < S.A.x)
                return false;
            if (B == S.B)
                return A.y < S.A.y;
            if (A == S.A)
                return B.y < S.B.y;
            return getSide(S.A.x, S.A.y) > 0;
        }

        long long getSide(long long x, long long y) const {
            return (y - A.y) * ((int)B.x - A.x) - (x - A.x) * ((int)B.y - A.y);
        }
    };

    Point P[N + 1];
    Segm S[N];
    int X[N], nrP, nrFile, nrSegm, startStep;
    vector<int> file[N];
    bool* use;

    int binSrcX(int x){
        int ans = 0;
        for (int step = startStep, aux = startStep ; step ; step >>= 1, aux = ans ^ step)
            if (aux < nrFile && X[aux] <= x)
                ans = aux;
        return ans;
    }

    bool isInside(vector<int>& v, int x, int y){
        if (v.empty() || S[ v[0] ].getSide(x, y) < 0)
            return false;
        unsigned int ans = 0;
        for (unsigned int step = startStep, aux = startStep ; step ; step >>= 1, aux = ans ^ step)
            if ( aux < v.size() && S[ v[aux] ].getSide(x, y) >= 0 )
                ans = aux;
        return (ans & 1) == 0 || S[ v[ans] ].getSide(x, y ) == 0;
    }

    void addSegment(int x){
        Segm A = Segm(P[x], P[x + 1]), B;
        use[x] = true;

        for (int i = 0 ; i < nrP ; i++){
            B = Segm(P[i], P[i + 1]);
            if (!use[i] && A < B)
                addSegment(i);
        }

        S[--nrSegm] = A;
    }

public:
    Poligon(){
        nrP = 0;
    }

    void add(int x, int y){
        P[nrP].x = x;
        P[nrP].y = y;
        nrP++;
    }

    void preprocesare(){
        ///DETERMINE STEP SIZE
        startStep = 1;
        while ( (startStep << 1) <= nrP )
            startStep <<= 1;
        ///INDEX BY X
        for (int i = 0 ; i < nrP ; i++)
            X[i] = P[i].x;
        sort(X, X + nrP);
        nrFile = 1;
        for (int i = 1 ; i < nrP ; i++)
            if (X[i] != X[i - 1])
                X[nrFile++] = X[i];
        ///CREATE SEGMENTS
        P[nrP] = P[0];
        nrSegm = nrP;
        use = (bool*)calloc(N, sizeof(bool));
        for (int i = 0 ; i < nrP ; i++)
            if (!use[i])
                addSegment(i);
        nrSegm = nrP;
        free(use);
        ///CREATE FILES
        int st, dr;
        for (int i = 0 ; i < nrP ; i++){
            st = binSrcX(S[i].A.x);
            dr = binSrcX(S[i].B.x);

            for (int j = st ; j < dr ; j++)
                file[j].push_back(i);
        }
    }

    bool query(int x, int y){
        int P = binSrcX(x);
        if (isInside( file[P], x, y ))
            return true;
        if (P && X[P] == x)
            return isInside( file[P - 1], x, y );
        return false;
    }
};

Poligon<800> P;

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

int main(){
    int n, nrQ, x, y;

    in >> n >> nrQ;
    for (int i = 1 ; i <= n ; i++){
        in >> x >> y;
        P.add(x, y);
    }

    P.preprocesare();

    int ans = 0;
    while (nrQ--){
        in >> x >> y;
        ans += P.query(x, y);
    }
    out << ans << "\n";

    return 0;
}