Cod sursa(job #1388131)

Utilizator retrogradLucian Bicsi retrograd Data 15 martie 2015 10:52:20
Problema Poligon Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#include<vector>

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;
    }
};

vector<Punct> Poligon;

bool check(Punct P) {
    var n = Poligon.size();
    bool isinside = 0;
    for(var i=1; i<n; i++) {
        //Tragem dreapta verticala

        Punct A = Poligon[i-1],
              B = Poligon[i];

        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));
    }
    Poligon.push_back(Poligon[0]);

    var sum = 0;

    while(m--) {
        fin >> x >> y;
        Punct P(x, y);
        sum += check(P);
    }

    fout << sum;

    return 0;
}