Cod sursa(job #2328767)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 26 ianuarie 2019 10:35:33
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct punct{
    double x, y;
    punct (int x, int y) : x(x), y(y){}
};

double f(punct M, punct A, punct B){
    return (M.x * (A.y - B.y) + M.y * (B.x - A.x) + A.x * B.y - A.y * B.x);
}

vector <punct> poligon;
vector <punct> query;
int n, m;
int AFIS = 0;

int main() {

    in >> n >> m;
    for (int i = 0; i < n; ++i) {
        double X, Y;
        in >> X >> Y;
        poligon.emplace_back (X, Y);
    }

    for (int i = 0; i < m; ++i) {
        int nr = 0;
        double X, Y;
        in >> X >> Y;
        punct P(X, Y);
        punct OUT(-1, -1);
        for (int j = 0; j < n - 1; ++j) {
            punct A = poligon[j];
            punct B = poligon[j + 1];

            if(f(A, P, OUT) * f(B, P, OUT) <= 0)
                nr++;
        }
        if(nr & 1)
            AFIS++;
    }

    out << AFIS << "\n";

    return 0;
}