Cod sursa(job #1388163)

Utilizator retrogradLucian Bicsi retrograd Data 15 martie 2015 11:33:15
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;
typedef int var;

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

struct Punct {
    var x, y;
    Punct(var a, var b) {
        x = a;
        y = b;
    }
};

typedef pair<Punct, Punct> ppp;
#define mp make_pair

vector<Punct> Poligon;
vector<Punct> Puncte;
vector<ppp> Sector[1600];
vector<var> PuncteX;

bool check(Punct P, var ind) {
    vector<ppp> &S = Sector[ind];
    //var n = S.size();
    bool isinside = 0;
    for(auto p : S) {
        //Tragem dreapta verticala

        Punct A = p.first,
              B = p.second;

        //if(A.x > B.x) swap(A, B);

        if(P.x <= A.x || P.x > B.x)
            continue;
        //Semnul determinantului
        //|  i     j   k|
        //|x2-x1 y2-y1 0|
        //|x-x1  y-y1  0|

        if((P.y-A.y)*(B.x-A.x) <= (P.x-A.x)*(B.y-A.y)) {
            isinside ^= 1;
        }

    }
    return isinside;
}

int main() {
    var n, m;
    var x, y;

    fin >> n >> m;
    for(var i=1; i<=n; i++) {
        fin>>x>>y;
        Poligon.push_back(Punct(x, y));
        if(find(PuncteX.begin(), PuncteX.end(), x) == PuncteX.end())
            PuncteX.push_back(x);
    }
    Poligon.push_back(Poligon[0]);

    const var INF = 100000;
    PuncteX.push_back(-INF);
    PuncteX.push_back(INF);
    sort(PuncteX.begin(), PuncteX.end());


    for(var p=2; p<PuncteX.size()-1; p++) {
        for(var i=1; i<=n; i++) {
            Punct A = Poligon[i],
                  B = Poligon[i-1];
            if(A.x > B.x) swap(A, B);

            if(A.x <= PuncteX[p-1] && B.x >= PuncteX[p]) {
                Sector[p-1].push_back(mp(A, B));
            }
        }
    }
/*
    for(var i=0; i<PuncteX.size()-1; i++) {
        fout<<"Sectorul : "<<i<<" dat de "<<PuncteX[i]<<" "<<PuncteX[i+1]<<" :\n";
        for(auto p : Sector[i]) {
            fout<<"|"<<p.first.x<<" "<<p.first.y<<", "<<p.second.x<<" "<<p.second.y<<"| ";
        }
        fout<<endl;
    }
*/

    var sum = 0;

    var MAX;
    var s = PuncteX.size() - 1;
    for(MAX=1; MAX<=PuncteX.size(); MAX<<=1);
    MAX >>= 1;

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

        var i, ind=0;
        for(i=MAX; i; i>>=1) {
            if(i+ind <= s && x >= PuncteX[i+ind])
                ind+=i;
        }
        //ind++;

        Punct P(x, y);
        //fout<<"Sectorul lui "<<x<<" "<<y<<" este "<<ind<<'\n';
        sum += check(P, ind);
    }

    fout << sum;

    return 0;
}