Cod sursa(job #1645837)

Utilizator SmarandaMaria Pandele Smaranda Data 10 martie 2016 14:01:08
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 808;
const double eps = 1.e-14;

struct Point {
    double x, y;
};

struct Fasie {
    double a, b, c;
    double xm;
};

class MyComp {
public:
    bool operator () (const Point &A, const Point &B) {
        return A.y - B.y <= -eps;
    }
};

class MyComp2 {
public:
    bool operator () (const Fasie &A, const Fasie &B) {
        return A.xm - B.xm <= -eps;
    }
};

int f;
double ny [N], ny2 [N];
Point P [N], b [N];
vector <Fasie> fasii [N];

int semn (Fasie F, Point A) {
    double cp;

    cp = F.a * A.x + F.b * A.y + F.c;
    if (fabs (cp) < eps)
        return 0;
    if (cp <= -eps)
        return -1;
    return 1;
}

int binarySearch (double value) {
    int step, i;

    for (i = 0, step = (1 << 10); step; step >>= 1)
        if (i + step <= f && b [i + step].y - value <= -eps)
            i = i + step;
    return i + 1;
}

int binarySearch1 (int k, Point C) {
    int step, i;

    for (i = -1, step = (1 << 10); step; step >>= 1)
        if (i + step < fasii [k].size () && semn (fasii [k][i + step], C) < 0)
            i = i + step;
    return i + 1;
}

Point intersect (Fasie F, double y) {
    Point I;

    I.y = y;
    I.x = (-(double)F.c - F.b * y) / F.a;
    return I;
}



int main () {
    int n, i, xc, yc, x, y, m, l, j, med, ans = 0, num, k, k1, cp, u;
    Fasie F;
    Point A, B, C;

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

    scanf ("%d%d", &n, &m);
    l = 0;
    for (i = 1; i <= n; i ++) {
        scanf ("%d%d", &x, &y);
        P [i].x = x;
        P [i].y = y;
        ny [++ l] = y;
    }

    sort (ny + 1, ny + 1 + l);
    ny2 [1] = ny [1];
    u = 1;
    for (i = 2; i <= l; i ++)
        if (ny [i] != ny [i - 1])
            ny2 [++ u] = ny [i];

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

    for (i = 1; i < u; i ++) {
        ++ f;
        A.x = ny [i];
        A.y = ny [i + 1];
        b [f] = A;
        for (j = 1; j <= n; j ++)
            if (P [j].y <= ny [i] && P [j + 1].y > ny [i]){
                F.a = P [j].y - P [j + 1].y;
                F.b = P [j + 1].x - P [j].x;
                F.c = P [j].x * P [j + 1].y - P [j + 1].x * P [j].y;
                A = intersect (F, ny [i]);
                B = intersect (F, ny [i + 1]);
                F.xm = (A.x + B.x) / 2;
                fasii [f].push_back (F);
            }
    }
    for (i = 1; i <= f; i ++)
        sort (fasii [i].begin (), fasii [i].end (), MyComp2 ());

    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &x, &y);
        C.x = x;
        C.y = y;
        k = binarySearch (y);

        k1 = binarySearch1 (k, C);
        if (k1 < fasii [k].size ()) {
            cp = semn (fasii [k][k1], C);
            if (cp == 0) {
                ans ++;
                continue;
            }
        }
        num = fasii [k].size () - (k1 + 1) + 1;
        if (num % 2) {
            ans ++;
        }
    }
    printf ("%d\n", ans);
    return 0;
}