Cod sursa(job #1088666)

Utilizator MyrmekoMeMarin Cristian MyrmekoMe Data 20 ianuarie 2014 18:48:52
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct point {
    int x, y;
} P[888];

vector <int> Bucket[888];
double A[888], B[888], C[888];
int OX[888], xx[888];

int curBucket;
struct comp {
    inline bool operator () (int i, int j) {
        int middle = OX[curBucket] + OX[curBucket + 1];
        double y1 = (-2.0 * C[i] - A[i] * middle) / B[i];
        double y2 = (-2.0 * C[j] - A[j] * middle) / B[j];
        return y2 - y1 > 0.000001;
    }
};

bool onLine;

bool check(int x0, int y0, int curLine) {
    if (A[curLine] * x0 + B[curLine] * y0 + C[curLine] == 0)
        onLine = 1;
    double lineY = (-C[curLine] - A[curLine] * x0) / B[curLine];
    return y0 >= lineY;
}

int main() {
    freopen("poligon.in", "r", stdin);
    freopen("poligon.out", "w", stdout);

    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        scanf("%d%d", &P[i].x, &P[i].y);
        xx[++xx[0]] = P[i].x;
    }
    P[N + 1] = P[1];
    for (int i = 1; i <= N; ++i) {
        A[i] = P[i].y - P[i + 1].y;
        B[i] = P[i + 1].x - P[i].x;
        C[i] = P[i].x * P[i + 1].y - P[i].y * P[i + 1].x;
    }
    sort(xx + 1, xx + xx[0] + 1);
    OX[++OX[0]] = xx[1];
    for (int i = 2; i <= xx[0]; ++i)
        if (xx[i] != OX[OX[0]])
            OX[++OX[0]] = xx[i];
    for (int i = 1; i <= OX[0]; ++i) {
        curBucket = i;
        for (int j = 1; j <= N; ++j)
            if (min(P[j].x, P[j + 1].x) <= OX[i] && OX[i] < max(P[j].x, P[j + 1].x))
                Bucket[i].push_back(j);
        sort(Bucket[i].begin(), Bucket[i].end(), comp());
    }

    int res = 0;
    while (M--) {
        int x0, y0;
        scanf("%d%d", &x0, &y0);
        if (x0 < OX[1] || x0 > OX[OX[0]])
            continue;
        curBucket = onLine = 0;
        for (int step = 10; step >= 0; --step)
            if (curBucket + (1 << step) <= OX[0] && OX[curBucket + (1 << step)] < x0)
                curBucket += (1 << step);
        int j = 0;
        for (int step = 10; step >= 0; --step)
            if (j + (1 << step) <= Bucket[curBucket].size() && check(x0, y0, Bucket[curBucket][j + (1 << step) - 1]))
                j += (1 << step);
        if (j % 2 == 1 || onLine == 1)
            ++res;
    }

    printf("%d\n", res);
    return 0;
}