Cod sursa(job #2328958)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 26 ianuarie 2019 11:40:07
Problema Poligon Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

pair<int,int> pref = {-1,-1};

vector <pair<int,int>> pct;
int n,m,x,y,sol;

int det(pair<int,int> &p1, pair<int,int> &p2, pair<int,int> &p3){
    long long rez = 1LL*(p2.first-p1.first)*(p3.second-p1.second) - 1LL*(p3.first-p1.first)*(p2.second-p1.second);

    //cout<<rez<<" ";

    if(rez<0)
        return -1;
    if(rez>0)
        return 1;
    return 0;
}

bool solve(pair <int,int> p){
    int u = 0;
    int aux;
    int d1, d2, d3, d4;

    for(int i = 0; i < n; ++i){
        d1 = det(p,pct[i],pct[i+1]);
        d2 = det(pref, pct[i], pct[i+1]);
        d3 = det(pct[i], p, pref);
        d4 = det(pct[i+1], p, pref);
        if(d1*d2<=0 && d3*d4<0)
            ++u;
    }

    //cout<<u<<"\n";
    return u%2;
}

int main()
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);

    scanf("%d %d", &n,&m);
    for(int i=0;i<n;++i){
        scanf("\n%d %d", &x, &y);
        pct.push_back({x,y});
    }
    pct.push_back(pct.front());

    for(int i = 0; i < m; ++i){
        scanf("\n%d %d", &x, &y);
        pref = {60001, y};
        if(solve({x,y}))
            ++sol;
    }

    cout<<sol;

    return 0;
}