Cod sursa(job #2328769)

Utilizator victorv88Veltan Victor victorv88 Data 26 ianuarie 2019 10:36:06
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct pct{
    int x, y;
}puncte_poligon[805],puncte_interioare[60005], punct_exterior;

int n, m, nr=0;

int calculare_det(pct a, pct b, pct c)
{
    return (a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y);
}

void verificare_punct(pct punct)
{
    int num=0;
    int val1, val2;
    int bal1, bal2;
    for (int i=1; i<=n; i++)
    {
        val1=calculare_det(punct,puncte_poligon[i],puncte_poligon[i+1]);
        val2=calculare_det(punct_exterior,puncte_poligon[i],puncte_poligon[i+1]);
        bal1=calculare_det(puncte_poligon[i],punct,punct_exterior);
        bal2=calculare_det(puncte_poligon[i+1],punct,punct_exterior);
        if (val1*val2<=0 && bal1*bal2<=0) {
            num++;
        }
    }
    if (num%2==1)
        nr++;
}

int main() {
    f >> n >> m;
    for (int i=1; i<=n; i++)
    {
        f >> puncte_poligon[i].x >> puncte_poligon[i].y;
    }
    for (int i=1; i<=m; i++)
    {
        f >> puncte_interioare[i].x >> puncte_interioare[i].y;
    }
    punct_exterior={-1,-1};
    puncte_poligon[n+1].x=puncte_poligon[1].x;
    puncte_poligon[n+1].y=puncte_poligon[1].y;
    for (int i=1; i<=m; i++)
    {
        verificare_punct(puncte_interioare[i]);
    }
    g << nr;
    return 0;
}