Cod sursa(job #773933)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 2 august 2012 21:28:14
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <cstdio>

#include <algorithm>

using namespace std;

struct punct {
    int x,y;
};

struct intersectie {
    double y1, y2, mid;
};

const int N = 805;
const double EPS = 1e-10;
const int INF = 0x3f3f3f3f;

int n, m, a, b, fasie, sol, fasii;
int x[N], nr[N];
punct p[N];
intersectie intersectii[N][N];


inline int cmp (intersectie a, intersectie b)
{
    if (a.mid + EPS < b.mid)
        return 1;
    return 0;
}

inline void makeStrips()
{
    for (int i = 1; i < fasii; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j].x <= x[i] && x[i + 1] <= p[j + 1].x) {
                double alfa, x1, x2, y1, y2;
                alfa = (double)(p[j + 1].y - p[j].y) / (double)(p[j + 1].x - p[j].x);
                
                x1 = x[i];
                y1 = alfa * (x1 - p[j].x) + p[j].y;

                x2 = x[i + 1];
                y2 = alfa * (x2 - p[j].x) + p[j].y;

                //intersectii[i][++nr[i]] = {y1, y2, (y1 + y2) / 2};
                intersectii[i][++nr[i]].y1 = y1;
                intersectii[i][nr[i]].y2 = y2;
                intersectii[i][nr[i]].mid = (y1 + y2) / 2.0;
            }
        }
        sort(intersectii[i] + 1, intersectii[i] + nr[i] + 1, cmp);
    }
}

inline int cauta_fasie(int a, int b)
{
    int l, r;
    l = 1;
    r = fasii - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (x[mid] <= a && a <= x[mid + 1])
            return mid;
        if (a < x[mid])
            r = mid - 1;
        else if (a > x[mid + 1])
            l = mid + 1;
    }
}

inline int verifica(int a, int b, int fasie)
{
    int l, r;
    l = 1;
    r = nr[fasie];
    
    while (l <= r) {
        int mid = l + (r - l) / 2;
        
        double x1 = x[fasie], x2 = x[fasie + 1];
        double y1 = intersectii[fasie][mid].y1, y2 = intersectii[fasie][mid].y2;
        double det1 = x1 * y2 + y1 * a + x2 * b - a * y2 - x2 * y1 - b * x1;
        y1 = intersectii[fasie][mid + 1].y1;
        y2 = intersectii[fasie][mid + 1].y2;
        double det2 = x1 * y2 + y1 * a + x2 * b - a * y2 - x2 * y1 - b * x1;

        if (det1 < EPS || det2 < EPS)
            return 1;

        if (det1 + EPS < 0.0 && det2 - EPS > 0.0) {
            if (mid % 2 == 0)
                return 0;
            else return 1;
        }

        if (det1 - EPS > 0.0)
            r = mid - 1;
        else if (det2 + EPS < 0.0)
            l = mid + 1;
    }
    return 0;
}

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

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &p[i].x, &p[i].y);
        x[i] = p[i].x;
    }
    p[n + 1] = p[1];
    
    sort(x + 1, x + n + 1);
    x[n + 1] = INF;
    for (int i = 1; i <= n; ++i)
        if (x[i] != x[i + 1])
            x[++x[0]] = x[i];
    
    fasii = x[0];
    makeStrips();

    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &a, &b);
        fasie = cauta_fasie(a, b);
        if (verifica(a, b, fasie)) {
            ++sol;
            fprintf(stderr, "%d ", i);
        }
    }

    printf("%d", sol);

    return 0;
}