Cod sursa(job #1546577)

Utilizator serbanSlincu Serban serban Data 8 decembrie 2015 11:50:24
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

vector< pair<int, int> > V;
vector< pair< pair<int, int>, pair<int, int> > > E;

long long det(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    return a.first * b.second + b.first * c.second + c.first * a.second
        - a.second * b.first - b.second * c.first - c.second * a.first;
}

bool cmp(pair< pair<int, int>, pair<int, int> > AA, pair< pair<int, int>, pair<int, int> > BB) {
    if(max(AA.first.first, AA.second.first) < max(BB.first.first, BB.second.first))
        return max(AA.first.second, AA.second.second) < max(BB.first.second, BB.second.second);
    return max(AA.first.first, AA.second.first) < max(BB.first.first, BB.second.first);
}

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

    int n, m;
    f >> n >> m;

    pair<int, int> aux;
    f >> aux.first >> aux.second;
    V.push_back(aux);
    for(int i = 1; i < n; i ++) {
        pair<int, int> aux;
        f >> aux.first >> aux.second;
        V.push_back(aux);
        E.push_back(make_pair(V[V.size() - 2], V[V.size() - 1]));
    }
    E.push_back(make_pair(V[V.size() - 1], V[0]));

    sort(E.begin(), E.end(), cmp);

    int nr = 0;
    for(int j = 1; j <= m; j ++) {
        pair<int, int> aux;
        f >> aux.first >> aux.second;
        int k = 0;
        for(int i = 0; i < E.size(); i ++) {
            int mx = max(E[i].first.first, E[i].second.first);
            int mxY = max(E[i].first.second, E[i].second.second);
            int mnY = min(E[i].first.second, E[i].second.second);

            if(aux.first <= mx && aux.second > mnY && aux.second < mxY)
                k ++;
            else if(aux.second >= mnY && aux.second <= mxY) {
                if((E[i].second.second == mxY && aux.second == mxY) ||
                  (E[i].first.second == mxY && aux.second == mxY))
                    k ++;
            }
        }
        if(k & 1)
            nr ++;
    }
    g << nr << "\n";
    return 0;
}