Cod sursa(job #1645618)

Utilizator SmarandaMaria Pandele Smaranda Data 10 martie 2016 13:05:04
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.19 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 Latura {
    double x1, y1, x2, y2;
};

struct Fasie {
    Point A, B;
    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;
Point P [N], b [N];
Latura L [N];
vector <Fasie> fasii [N];

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, double value) {
    int step, i;

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

Point intersect (Latura d, double y) {
    Point I;
    double a, b, c;

    a = d.y1 - d.y2;
    b = d.x2 - d.x1;
    c = d.x1 * d.y2 - d.x2 * d.y1;

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

int ccw (Point A, Point B, Point C) {
    double cp;

    cp = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
    if (cp <= -eps)
        return -1;
    if (fabs (cp) < eps)
        return 0;
    return 1;
}

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

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

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

    l = 0;
    P [n + 1] = P [1];
    for (i = 1; i <= n; i ++)
        if (P [i].y < P [i + 1].y) {
            L [++ l].x1 = P [i].x;
            L [l].y1 = P [i].y;
            L [l].x2 = P [i + 1].x;
            L [l].y2 = P [i + 1].y;
        }
        else {
            L [++ l].x2 = P [i].x;
            L [l].y2 = P [i].y;
            L [l].x1 = P [i + 1].x;
            L [l].y1 = P [i + 1].y;

        }

    sort (P + 1, P + 1 + n, MyComp ());

    for (i = 1; i < n; i ++)
        if (P [i].y != P [i + 1].y) {
            ++ f;
            A.x = P [i].y;
            A.y = P [i + 1].y;
            b [f] = A;
            for (j = 1; j <= l; j ++)
                if (L [j].y1 <= P [i].y && P [i + 1].y <= L [j].y2) {
                    A = intersect (L [j], P [i].y);
                    B = intersect (L [j], P [i + 1].y);
                    F.A = A;
                    F.B = B;
                    F.xm = ((double)A.x + B.x) / 2;
                    fasii [f].push_back (F);
                }
        }

  //  printf ("%d\n", f);
    for (i = 1; i <= f; i ++) {
       // printf ("Intre %f si %f cu segmentele : ", fasii [i][0].A.y, fasii [i][0].B.y);
        sort (fasii [i].begin (), fasii [i].end (), MyComp2 ());
       /* for (j = 0; j < fasii [i].size (); ++ j)
            printf ("(%f, %f) ", fasii [i][j].A.x, fasii [i][j].B.x);
        printf ("\n");*/
    }

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

        k1 = binarySearch1 (k, x);
        if (k1 != 0) {
            cp = ccw (fasii [k][k1 - 1].A, fasii [k][k1 - 1].B, C);
            if (cp > 0)
                num ++;
            if (cp == 0) {
                 ans ++;
               // printf ("%d %d\n", x, y);
                continue;
            }
        }
        if (k1 < fasii [k].size ()) {
            cp = ccw (fasii [k][k1].A, fasii [k][k1].B, C);
            if (cp == 0) {
                ans ++;
             //   printf ("%d %d\n", x, y);
                continue;
            }
        }
        num = num + fasii [k].size () - (k1 + 1) + 1;
        if (num % 2) {
            ans ++;
          //  printf ("%d %d\n", x, y);
        }
    }
    printf ("%d\n", ans);
    return 0;
}