Cod sursa(job #1213760)

Utilizator mariusn01Marius Nicoli mariusn01 Data 28 iulie 2014 22:22:10
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.01 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#define DIM 810
#define EPS 0.000000001
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");

vector<pair<int, int> > V;
vector<pair< pair<int, int>, pair<int, int> > > M;
vector<pair< pair<double, double>, pair<double, double> > > P[DIM];
multiset<int> S;
multiset<int>::iterator its;
vector<int> X;
pair<double, double> q, Q;
int n, m, x, y, xa, ya, X0, Y0, i, j, ok, p, u, sol, mid, k;
double s;
inline int modul(int a) {
    return ( a>0 ? a: -a );
}

int cmp(const pair< pair<int, int>, pair<int, int> > &a, const pair< pair<int, int>, pair<int, int> > &b) {
    return a.first.second+a.second.second < b.first.second+b.second.second;
}

double semn(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c) {
    return (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
}

int main() {
    fin>>n>>m;
    fin>>xa>>ya;
    X0 = xa;Y0 = ya;
    S.insert(X0);
    for (i=2;i<=n;i++) {
        fin>>x>>y;
        S.insert(x);
        if ((xa < x) || ((xa == x) && (ya < y)))
            M.push_back(make_pair( make_pair(xa, ya) , make_pair(x, y) ));
        else
            M.push_back(make_pair( make_pair(x, y) , make_pair(xa, ya) ));
        xa = x;
        ya = y;
    }
    if ((xa < X0)|| ((xa == X0) && (ya < Y0)))
        M.push_back(make_pair( make_pair(xa, ya) , make_pair(X0, Y0) ));
    else
        M.push_back(make_pair( make_pair(X0, Y0) , make_pair(xa, ya) ));

    for (its = S.begin(); its!=S.end(); its++) {
        X.push_back(*its);
    }

    for (i=0;i<X.size()-1;i++) {
        for (j=0;j<M.size();j++) {
            if (M[j].first.first <= X[i] && M[j].second.first >=X[i+1]) {
                if (M[j].first.first != M[j].second.first) {
                    q.second = M[j].first.second + ((M[j].second.second-M[j].first.second) * (X[i]-M[j].first.first))/(double)(M[j].second.first-M[j].first.first);
                    Q.second = M[j].first.second + ((M[j].second.second-M[j].first.second) * (X[i+1]-M[j].first.first))/(double)(M[j].second.first-M[j].first.first);
                } else {
                    q.second = M[j].first.second;
                    Q.second = M[j].second.second;
                }
                q.first = X[i];
                Q.first = X[i+1];
                P[i].push_back(make_pair(q, Q));
            }
        }

    }



    for (i=0;i<X.size()-1;i++)
        sort(P[i].begin(), P[i].end(), cmp);

    for (i=1;i<=m;i++) {
        fin>>x>>y;
        // caut fasia in care se gaseste punctul
        if (x < X[0] || x > X[X.size()-1]) {
            continue;
        }
        p = 0;
        u = X.size()-1;
        while (p <= u) {
            mid = (p+u)/2;
            if (x >= X[mid] && x<=X[mid+1]) {
                u = mid-1;
                continue;
            }
            if (x < X[mid])
                u = mid-1;
            else
                p = mid+1;
        }

        //caut in fasia X[mid], X[mid+1]

        pair<double, double>t = make_pair((double)x,(double)y);

        mid = p;

        if(semn(P[mid][0].first, P[mid][0].second, t) < 0)
            continue;

        if (semn( P[mid][ P[mid].size()-1 ].first, P[mid][ P[mid].size()-1 ].second, t ) > 0)
            continue;

        ok = 0;
        p = 0;
        u = P[mid].size()-1;
        while (p<=u) {
            k = (p+u)/2;
            s = semn(P[mid][k].first, P[mid][k].second, t);
            if (s < EPS && s>-EPS)
                s = 0;
            if (s == 0 && t.second >= P[mid][k].first.second && t.second<=P[mid][k].second.second) {
                sol++;
                ok = 1;
                break;
            }
            if (s > 0)
                p = k+1;
            else
                u = k-1;

        }

        if (ok)
            continue;
        if (u%2 == 0)
            sol++;
    }
    fout<<sol<<"\n";
    return 0;
}