Proiect AF - Poligon

// https://www.infoarena.ro/problema/poligon
// Se citesc varfurile unui poligon si M puncte din fisier.
// Determinati cate dintre cele M puncte se gasesc in planul poligonului (inclusiv pe laturile acestuia).

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

vector<int> v[100];

bool vertical;
int nrVfPoligon, k, abscisa[100];
double mid;

struct Punct
{
    int coordX, coordY;
} poligon[100];

void citireVfPoligon()
{
    for (int i = 1; i <= nrVfPoligon; i++)
    {
        fin >> poligon[i].coordX >> poligon[i].coordY;
        abscisa[i] = poligon[i].coordX;
    }
}

double eval(Punct p1, Punct p2, double m)
{
    return p1.coordY + ((double)p2.coordY - p1.coordY) * (m - p1.coordX) / ((double)p2.coordX - p1.coordX);
}

bool comp(int coordX, int coordY)
{
    return eval(poligon[coordX], poligon[coordX + 1], mid) < eval(poligon[coordY], poligon[coordY + 1], mid);
}

long long Determinant(Punct p1, Punct p2, Punct p3)
{
    //Determinant Sarrus
    return 1LL * p1.coordX * p2.coordY + 1LL * p2.coordX * p3.coordY + 1LL * p3.coordX * p1.coordY
        - 1LL * p1.coordX * p3.coordY - 1LL * p2.coordX * p1.coordY - 1LL * p3.coordX * p2.coordY;
}

bool compare(Punct p1, Punct p2)
{
    if (p1.coordX == p2.coordX)
        return p1.coordY < p2.coordY;
    return p1.coordX < p2.coordX;
}

bool OK(int i, Punct p)
{
    long long det;

    if (compare(poligon[i], poligon[i + 1]))
        det = Determinant(poligon[i], poligon[i + 1], p);
    else
        det = Determinant(poligon[i + 1], poligon[i], p);

    if (det == 0)
    {
        vertical = true;
        return 1;
    }
    return det > 0;
}

void precompute()
{
    sort(abscisa + 1, abscisa + nrVfPoligon + 1);

    abscisa[0] = -1;
    poligon[nrVfPoligon + 1] = poligon[1];

    for (int i = 1; i <= nrVfPoligon; i++)
        if (abscisa[i] != abscisa[k])
            abscisa[++k] = abscisa[i];

    abscisa[k + 1] = abscisa[k] + 100;

    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= nrVfPoligon; j++)
            if ((poligon[j].coordX <= abscisa[i] && abscisa[i + 1] <= poligon[j + 1].coordX) ||
                (poligon[j + 1].coordX <= abscisa[i] && abscisa[i + 1] <= poligon[j].coordX))
                v[i].push_back(j);

        mid = ((double)abscisa[i] + (double)abscisa[i + 1]) / 2;

        sort(v[i].begin(), v[i].end(), comp);
    }
}

void compute(int m, int& nrIntrusi)
{
    for (int i = 1; i <= m; i++)
    {
        Punct PunctCurent = { 0 };
        fin >> PunctCurent.coordX >> PunctCurent.coordY;

        int pozitie = 0, contor = -1;

        for (int i = 1 << 9; i; i >>= 1)
            if (pozitie + i <= k && abscisa[pozitie + i] < PunctCurent.coordX)
                pozitie += i;

        vertical = 0;

        for (int i = 1 << 9; i; i >>= 1)
            if (contor + i < v[pozitie].size() && OK(v[pozitie][i + contor], PunctCurent))
                contor += i;
        contor++;
        nrIntrusi += ((contor & 1) | (vertical));
    }
}

int main()
{
    int m, nrIntrusi = 0;

    fin >> nrVfPoligon >> m;
    citireVfPoligon();

    precompute();
    compute(m, nrIntrusi);
    fout << nrIntrusi;

    fin.close();
    fout.close();
    return 0;
}