Cod sursa(job #1488650)

Utilizator retrogradLucian Bicsi retrograd Data 19 septembrie 2015 14:00:45
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> Blocks;
vector<vector<int>> LR, RL, Vert;

int n;

bool Taken[100000];
int X[1000], Y[1000];

int det(int i, int x, int y) {
    int a = i, b = i-1;
    if(X[a] < X[b])
        swap(a, b);

    return (X[a] - X[b]) * (y - Y[b]) - (Y[a] - Y[b]) * (x - X[b]);
}

#define all(v) v.begin(), v.end()

int bsrc(vector<int> &L, int x, int y) {
    int pos = -1, i;
    for(i=1; i<=L.size(); i<<=1);
    for(i>>=1; i; i>>=1) {
        if(i + pos < L.size() && det(L[i+pos], x, y) > 0)
            pos += i;
    }

    return pos;
}


bool onBorder(int x, int y) {
    for(int i=1; i<=n; i++)
        if(det(i, x, y) == 0) {
            if(x >= min(X[i-1], X[i]) && x <= max(X[i-1], X[i]) &&
               y >= min(Y[i-1], Y[i]) && y <= max(Y[i-1], Y[i]))
                return 1;
        }
    return 0;
}

bool inPolygon(int x, int y) {
    int block = upper_bound(all(Blocks), x) - Blocks.begin() - 1;
    int pos1 = bsrc(LR[block], x, y);

    block = lower_bound(all(Blocks), x) - Blocks.begin();
    int pos2 = bsrc(RL[block], x, y);

    int pos3 = -1;
    if(Blocks[block] == x)
        pos3 = upper_bound(all(Vert[block]), y) - Vert[block].begin() - 1;

    return (pos1 + pos2 + pos3) % 2 == 0;
}


int main() {

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

    int m, x, y;
    fin>>n>>m;

    Blocks.push_back(0); Taken[0] = 1;
    Blocks.push_back(60000); Taken[60000] = 1;

    for(int i=1; i<=n; i++) {
        fin>>X[i]>>Y[i];
        if(!Taken[X[i]])
            Blocks.push_back(X[i]), Taken[X[i]] = 1;
    }
    X[0] = X[n]; Y[0] = Y[n];

    sort(all(Blocks));
    LR.resize(Blocks.size(), vector<int>());
    RL.resize(Blocks.size(), vector<int>());
    Vert.resize(Blocks.size(), vector<int>());

    for(int i=1; i<=n; i++) {
        int block = lower_bound(all(Blocks), X[i-1]) - Blocks.begin();
        if(X[i-1] < X[i]) {
            while(Blocks[block] != X[i]) {
                LR[block].push_back(i);
                block++;
            }
        } else if(X[i-1] > X[i]) {
            while(Blocks[block] != X[i]) {
                RL[block].push_back(i);
                block--;
            }
        } else {
            if(Y[i-1] < Y[i]) Vert[block].push_back(Y[i-1]);
            else              Vert[block].push_back(Y[i] + 1);
        }
    }

    auto cmp = [&x] (int a, int b) {

        int64_t term1 = 1LL * (X[b] - X[b-1]) *
            (Y[a-1] * (X[a] - X[a-1]) + (x - X[a-1]) * (Y[a] - Y[a-1]));
        int64_t term2 = 1LL * (X[a] - X[a-1]) *
            (Y[b-1] * (X[b] - X[b-1]) + (x - X[b-1]) * (Y[b] - Y[b-1]));

        return term1 < term2;
    };

    for(int i=0; i<Blocks.size(); i++) {
        x = Blocks[i];
        sort(all(LR[i]), cmp);
        sort(all(RL[i]), cmp);
        sort(all(Vert[i]));
    }

//    for(int i=0; i<Blocks.size(); i++) {
//        cerr<<Blocks[i]<<": LR ";
//        for(auto x : LR[i]) {
//            cerr<<x<<" ";
//        }
//        cerr<<"; RL ";
//        for(auto x : RL[i]) {
//            cerr<<x<<" ";
//        }
//        cerr<<endl;
//    }

    int interior = 0;

    while(m--) {
        fin>>x>>y;

        if(onBorder(x, y) || inPolygon(x, y)) {
            interior++;
            cerr<<x<<" "<<y<<'\n';
        }


    }

    fout<<interior;

    return 0;
}