Cod sursa(job #1506856)

Utilizator mariusn01Marius Nicoli mariusn01 Data 21 octombrie 2015 00:25:37
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.71 kb
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#define DIM 810
#define EPS 0.000000001
using namespace std;
FILE *fin = fopen("poligon.in","r");
FILE *fout = fopen("poligon.out","w");
 
vector<pair<int, int> > V;
vector<pair< pair<int, int>, pair<int, int> > > M;
vector<pair< pair<double, double>, pair<double, double> > > P[DIM];
set<int> S;
set<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;
 
 
int cmp(const pair< pair<double, double>, pair<double, double> > &a, const pair< pair<double, double>, pair<double, double> > &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() {
    fscanf(fin,"%d%d",&n,&m);
    fscanf(fin,"%d%d",&xa,&ya);
 
    X0 = xa;Y0 = ya;
    S.insert(X0);
    for (i=2;i<=n;i++) {
        fscanf(fin,"%d%d",&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 (j=0;j<M.size();j++) {
        ok = 0;
        for (i=0;i<X.size()-1;i++) {
            if (M[j].first.first <= X[i] && M[j].second.first >=X[i+1]) {
                if (ok == 0) {
                    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));
                } else {
                    q = Q;
                    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+1]-M[j].first.first))/(double)(M[j].second.first-M[j].first.first);
                    } else {
                        Q.second = M[j].second.second;
                    }
                    Q.first = X[i+1];
                    P[i].push_back(make_pair(q, Q));
 
                }
                ok++;
            }
        }
 
    }
 
    for (i=0;i<X.size()-1;i++)
        sort(P[i].begin(), P[i].end(), cmp);
 
    for (i=1;i<=m;i++) {
        fscanf(fin,"%d%d",&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)>>1);
            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)>>1);
            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++;
    }
    fprintf(fout,"%d\n",sol);
 
    return 0;
}