Cod sursa(job #868750)

Utilizator mihai995mihai995 mihai995 Data 31 ianuarie 2013 16:26:54
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 805;
const int M = 60005;

struct Punct{
    int x, y;

    Punct(){
        x = y = 0;
    }

    Punct(int _x, int _y){
        x = _x;
        y = _y;
    }

    inline bool operator<(const Punct& P) const{
        return x < P.x;
    }
};

struct Dreapta{
    int a, b, c;
    double ord;

    Dreapta(){
        a = b = c = 0;
    }

    Dreapta(Punct A, Punct B, int x){
        a = A.y - B.y;
        b = B.x - A.x;
        c = A.x * B.y - A.y * B.x;

        if (b < 0){
            a = -a;
            b = -b;
            c = -c;
        }

        ord = -(double)(a * x + c) / b;
    }

    int operator[](Punct P){
        return a * P.x + b * P.y + c;
    }

    inline bool operator<(const Dreapta& D) const {
        return ord < D.ord;
    }
};

class Fasie{
    Dreapta a[N];
    int n, st, dr;

public:
    void init(int x, int y){
        n = 0;
        st = x;
        dr = y;
    }

    void insert(Punct X, Punct Y){
        a[++n] = Dreapta(X, Y, st);
    }

    void prepare(){
        sort(a + 1, a + n + 1);
    }

    bool inside(Punct P){
        int val = -1;

        for (int step = 1 << 9 ; step ; step >>= 1)
            if (val + step <= n && a[val + step][P] >= 0)
                val += step;

        if (a[val][P] == 0)
            return true;

        return val & 1;
    }
};

class Vertical{
    vector<Punct> a[M];

public:
    void insert(int x, int y1, int y2){
        if (y1 > y2)
            swap(y1, y2);

        a[x].push_back(Punct(y1, y2));
    }

    void prepare(){
        for (int i = 0 ; i < M ; i++)
            if (!a[i].empty())
                sort(a[i].begin(), a[i].end());
    }

    bool inside(Punct P){
        vector<Punct>& v = a[P.x];

        if (v.empty())
            return false;

        int val = 0;

        for (int step = 1 << 9 ; step ; step >>= 1)
            if (val + step < v.size() && v[val + step].x <= P.y)
                val += step;

        return v[val].x <= P.y && P.y <= v[val].y;
    }
};

Fasie fasie[N];
Vertical V;
Punct P[N];
int X[N], n;

ifstream in("poligon.in");
ofstream out("poligon.out");

void cleanup(int X[], int n){
    sort(X + 1, X + n + 1);

    X[0] = 1;

    for (int i = 2 ; i <= n ; i++)
        if (X[i] != X[i - 1])
            X[++X[0]] = X[i];
}

int bsearch(int v[], int x){
    int val = 0;

    for (int step = 1 << 9 ; step ; step >>= 1)
        if (val + step <= v[0] && v[val + step] <= x)
            val += step;

    return val;
}

void compute(Fasie& F, int st, int dr){
    F.init(st, dr);

    for (int i = 1 ; i <= n ; i++)
        if (P[i].x != P[i + 1].x)
            F.insert(P[i], P[i + 1]);

    F.prepare();
}

int main(){
    Punct p;
    int m;

    in >> n >> m;

    for (int i = 1 ; i <= n ; i++){
        in >> P[i].x >> P[i].y;

        X[i] = P[i].x;
    }

    P[n + 1] = P[1];

    cleanup(X, n);

    for (int i = 1 ; i < n ; i++)
        compute(fasie[i], X[i], X[i + 1]);

    for (int i = 1 ; i <= n ; i++)
        if (P[i].x == P[i + 1].x)
            V.insert(P[i].x, P[i].y, P[i + 1].y);

    V.prepare();

    int ans = 0;

    while (m--){
        in >> p.x >> p.y;

        ans += (V.inside(p) || fasie[bsearch(X, p.x)].inside(p));
    }

    out << ans << "\n";

    return 0;
}