Cod sursa(job #1044461)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 29 noiembrie 2013 21:53:08
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.46 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;
inline bool comp(int i, int j) {
    int middle = (OX[i] + OX[i + 1]);
    double y1 = (-2 * C[i] - A[i] * middle) / B[i];
    middle = (OX[j] + OX[j + 1]);
    double y2 = (-2 * C[j] - A[j] * middle) / B[j];
    return y2 - y1 > 0.000001;
}

bool onLine;

inline int ccw(point A, point B, point C) {
    return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}

bool check(int x0, int y0, int curLine) {
    point tmp; tmp.x = x0; tmp.y = y0;
    onLine = 0;
    if (ccw(tmp, P[curLine], P[curLine + 1]) == 0)
        onLine = 1;
    double lineY = (-C[curLine] - A[curLine] * x0) / B[curLine];
    return (y0 - lineY >= 0.00001 || 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 = 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", res);
    return 0;
}