Cod sursa(job #594718)

Utilizator SpiderManSimoiu Robert SpiderMan Data 8 iunie 2011 23:52:12
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
# include <algorithm>
# include <cstdio>
# include <cmath>
# include <set>
# include <vector>
using namespace std;

# define x first
# define y second

typedef pair <int, int> PR ;
typedef set < pair <int, PR> > ST;
typedef ST :: iterator IT;
const char *FIN = "poligon.in", *FOU = "poligon.out" ;
const int MAX = 805, oo = 100000;

ST Set ;
PR P[MAX] ;
vector <int> A, V[MAX] ;
int N, M, solution ;
double mij ;

inline double cmp (int i, double mij) {
    double cst = (1.0 * P[i + 1].y - P[i].y) / (1.0 * P[i + 1].x - P[i].x) ;
    return cst * mij + 1.0 * P[i].y - cst * P[i].x ;
}

inline bool comp (int i, int j) {
    return cmp (i, mij) < cmp (j, mij) ;
}

int exista (int i, int X, int Y) {
    int sol = -1 ;
    for (int st = 0, dr = V[i].size () - 1; st <= dr; ) {
        int mij = st + dr >> 1;
        if (cmp (V[i][mij], X) <= Y) {
            sol = mij, st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }
    if (sol >= 0 && cmp (V[i][sol], X) <= Y) return 1;
    if (sol + 1 < (int) V[i].size () && cmp (V[i][sol + 1], X) <= Y) return 1;
    return (sol & 1) == 0 ;
}

int main (void) {
    freopen (FIN, "r", stdin) ;

    scanf ("%d %d", &N, &M), A.push_back (-1) ;
    for (int i = 1; i <= N; ++i) {
        scanf ("%d %d", &P[i].x, &P[i].y);
        A.push_back (P[i].x);
    }
    P[N + 1].x = P[1].x, P[N + 1].y = P[1].y;
    sort (A.begin (), A.end ());
    A.resize (unique (A.begin (), A.end ()) - A.begin ()) ;
    A[A.size ()] = oo;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0, k = A.size (); j < k; ++j) {
            if (min (P[i].x, P[i + 1].x) <= A[j] && A[j + 1] <= max (P[i].x, P[i + 1].x))
                V[j].push_back (i);
            if (P[i].x == P[i + 1].x && P[i].x == A[j])
                Set.insert (make_pair (A[j], make_pair (min (P[i].y, P[i + 1].y), max (P[i].y, P[i + 1].y))));
        }
        Set.insert (make_pair (P[i].x, make_pair (P[i].y, P[i].y))) ;
    }
    for (int i = 0, j = A.size (); i < j; ++i) {
        mij = (A[i] + A[i + 1]) / 2.0 ;
        sort (V[i].begin (), V[i].end (), comp) ;
    }
    for (int X, Y; M; --M) {
        scanf ("%d %d", &X, &Y) ;
        int poz = upper_bound (A.begin (), A.end (), X) - A.begin () - 1 ;
        if (exista (poz, X, Y)) {
            ++solution ;
            continue ;
        }
        if (A[poz] == X) {
            IT it = Set.upper_bound (make_pair (X, make_pair (Y, oo))) ;
            if (it != Set.begin ()) {
                solution += (--it) -> x == X && it -> y.x <= Y && Y <= it -> y.y;
            }
        }
    }
    fprintf (fopen (FOU, "w"), "%d", solution) ;
}