Cod sursa(job #2328948)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 26 ianuarie 2019 11:36:22
Problema Poligon Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>

#include <fstream>



using namespace std;



ifstream in("poligon.in");

ofstream out("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;

    long long val1, val2;

    long long 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() {

    in >> n >> m;

    for (int i = 1; i <= n; i++) {

        in >> puncte_poligon[i].x >> puncte_poligon[i].y;

    }

    for (int i = 1; i <= m; i++) {

        in >> 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]);

    }

    out << nr << '\n';

    return 0;

}