Cod sursa(job #2329358)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 26 ianuarie 2019 16:57:38
Problema Poligon Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#define MAXN 8010

using namespace std;

struct point {
    int x, y;
}area[MAXN], refPoint = {88069, 87803};

int n, m, sol = 0;

long long det(point pt1, point pt2, point pt3) {
    return 1ll * (1ll * (pt1.x - pt3.x) * (pt2.y - pt3.y) - 1ll * (pt2.x - pt3.x) * (pt1.y - pt3.y));
}

bool verify(point pt1, point pt2, point pt3, point pt4) {
    long long det1, det2;
    det1 = det(pt1, pt2, pt3);
    det2 = det(pt1, pt2, pt4);
    if ((det1 * det2) > 0)
        return false;
    det1 = det(pt3, pt4, pt1);
    det2 = det(pt3, pt4, pt2);
    if ((det1 * det2) > 0)
        return false;
    return true;
}

void solve(point input) {
    int nr = 0;
    for (int i = 0; i < n; i++) {
        if (verify(input, refPoint, area[i], area[(i + 1) % n])) {
            nr++;
        }
    }
    if (nr % 2)
        sol++;
}

void readData() {
    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 input;
        fin >> input.x >> input.y;
        solve(input);
    }
}

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

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