Cod sursa(job #2328916)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 26 ianuarie 2019 11:26:26
Problema Poligon Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f1("poligon.in");
ofstream f2("poligon.out");

int n,m,minx=999999,miny=999999;
vector<pair<int,int>> varfuri, infractiuni;


long long determinant(int xa, int ya, int xb, int yb, int xc, int yc){
    return (xa - xc)*(yb - yc) - (xb - xc)*(ya - yc);
}

bool amInteresctie(int x, int y){
    int counter = 0;
    for(int i=0;i<n-1;i++){
        long long punct = determinant(varfuri[i].first, varfuri[i].second, varfuri[i+1].first, varfuri[i+1].second, x, y);
        long long punctFix = determinant(varfuri[i].first, varfuri[i].second, varfuri[i+1].first, varfuri[i+1].second, minx, miny);
        long long primaComparatie = punct * punctFix;
        if(primaComparatie > 0)
            continue;
        punct = determinant(minx, miny, x, y, varfuri[i].first, varfuri[i].second);
        punctFix = determinant(minx, miny, x, y, varfuri[i+1].first, varfuri[i+1].second);
        if(punctFix == 0) continue;
        long long douaComparatie = punct * punctFix;
        if(douaComparatie <= 0) ++counter;
    }
    return counter % 2 != 0;
}


int main() {
    f1>>n>>m;
    int x,y;
    for(int i=0;i<n;i++){
        f1>>x>>y;
        if(x<minx) minx = x;
        if(y<miny) miny = y;
        varfuri.emplace_back(x,y);
    }
    minx--;
    miny--;
    int puncteInauntru = 0;
    for(int i=0;i<m;i++){
        f1>>x>>y;
        if(amInteresctie(x,y)) ++puncteInauntru;
    }
    f2<<puncteInauntru<<"\n";
    return 0;
}