Cod sursa(job #774037)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 3 august 2012 11:25:26
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.7 kb
#include <cmath>
#include <cstdio>

#include <algorithm>

using namespace std;

struct punct {
    int x,y;
};

struct intersectie {
    double x1, x2, 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) {
            //fprintf(stderr, "strips i = %d j = %d x[i] = %d p[j].x = %d x[i + 1] = %d p[j + 1].x = %d\n", i, j, x[i], p[j].x, x[i + 1], p[j + 1].x);
            if ((p[j].x <= x[i] && x[i + 1] <= p[j + 1].x) || (p[j].x >= x[i + 1] && p[j + 1].x <= x[i])){
                //fprintf(stderr, "OK\n");
                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;
                intersectii[i][nr[i]].x1 = x1;
                intersectii[i][nr[i]].x2 = x2;
            }
            if ((p[j].x == x[i] && p[j + 1].x == x[i]) || (p[j].x == x[i + 1] && p[j + 1].x == x[i + 1])) {
                intersectii[i][++nr[i]].y1 = p[j].y;
                intersectii[i][nr[i]].y2 = p[j + 1].y;
                intersectii[i][nr[i]].mid = ((double)p[j].y + p[j + 1].y) / 2.0;
                intersectii[i][nr[i]].x1 = intersectii[i][nr[i]].x2 = p[j].x;
            }
        }
        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 = intersectii[fasie][mid].x1, x2 = intersectii[fasie][mid].x2;
        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;
        x1 = intersectii[fasie][mid + 1].x1;
        x2 = intersectii[fasie][mid + 1].x2;
        double det2 = x1 * y2 + y1 * a + x2 * b - a * y2 - x2 * y1 - b * x1;
        //fprintf(stderr, "%d %lf %lf\n", mid, intersectii[fasie][mid].y1, intersectii[fasie][mid].y2);
        if (fabs(det1) < EPS || fabs(det2) < EPS) {
            //fprintf(stderr, "PE Muchie");
            return 1;
        }

        if (det1 < 0 && det2 > 0) {
            //fprintf(stderr, "AJUNS AICI!");
            if (intersectii[fasie][mid].x1 != intersectii[fasie][mid].x2) {
                if (mid % 2 == 0)
                    return 0;
                else return 1;
            }
            else {
                if ((mid - 1) % 2 == 0)
                    return 0;
                else return 1;
            }
        }

        if (det1 > 0)
            r = mid - 1;
        else if (det2 < 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 <= fasii; ++i) {
        for (int j = 1; j <= nr[i]; ++j)
            fprintf(stderr, "%lf %lf\t", intersectii[i][j].y1, intersectii[i][j].y2);
        fprintf(stderr, "\n");
    }*/
    //fprintf(stderr, "fasia 8 %lf %lf %lf %lf\n", intersectii[8][1].y1, intersectii[8][1].y2, intersectii[8][2].y1, intersectii[8][2].y2); 
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &a, &b);
        fasie = cauta_fasie(a, b);
        //fprintf(stderr, "%d", fasie);
        if (verifica(a, b, fasie)) {
            ++sol;
            //fprintf(stderr, "%d ", i);
        }
    }

    printf("%d\n", sol);

    return 0;
}