Cod sursa(job #2328878)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 26 ianuarie 2019 11:13:11
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#define MAXN 810
#define MAXM 60010

using namespace std;

struct point {
    int x, y;
}area[MAXN], negPoint = {-1, -1};

int n, m, sol = 0;

int det(point a, point b, point x) {
    return ((a.x - x.x) * (b.y - x.y) - (b.x - x.x) * (a.y - x.y));
}

bool verify(point a, point b, point c, point d) {
    long long det1, det2;
    det1 = det(c, d, a);
    det2 = det(c, d, b);
    if ((det1 * det2) < 0)
        return false;
    det1 = det(a, b, c);
    det2 = det(a, b, d);
    if ((det1 * det2) <= 0)
        return false;
    return true;
}

bool solve(point pt) {
    int nr = 0;
    for (int i = 0; i < n; i++) {
        if (verify(pt, negPoint, area[i], area[i + 1]))
            nr++;
    }
    if (verify(pt, negPoint, area[n - 1], area[0]))
        nr++;
    if (nr % 2)
        return true;
    return false;
}

void readInput() {
    ifstream fin("poligon.in");
    fin >> n >> m;
    for (int i = 0; i < n; i++) {
        fin >> area[i].x >> area[i].y;
    }
    for (int i = 0; i < m; i++) {
        point in;
        fin >> in.x >> in.y;
        if (solve(in))
            sol++;
    }
}

void printSolution() {
    ofstream fout("poligon.out");
    fout << sol << "\n";
}

int main() {
    readInput();
    printSolution();
    return 0;
}