Cod sursa(job #1213826)

Utilizator mariusn01Marius Nicoli mariusn01 Data 29 iulie 2014 00:21:30
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 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<long long, long long> > V;
vector<pair< pair<long long, long long>, pair<long long, long long> > > M;
vector<pair< pair<double, double>, pair<double, double> > > P[DIM];
set<long long> S;
set<long long>::iterator its;
vector<long long> X;
pair<double, double> q, Q;
long long n, m, x, y, xa, ya, X0, Y0, i, j, ok, p, u, sol, mid, k;
double s;


long long cmp(const pair< pair<double, double>, pair<double, double> > &a, const pair< pair<long long, long long>, pair<long long, long long> > &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-(double)M[j].first.second) * ((double)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-(double)M[j].first.second) * ((double)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) <= 0 ) {
                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;
}