Cod sursa(job #2817009)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 12 decembrie 2021 18:20:12
Problema Poligon Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.84 kb
#include <stdio.h>
#include <math.h>
const int MAXN = 801;
int n, m, i, j, NR, x0;
struct punct { int x, y; } pct[MAXN];
struct latura { punct a, b; } lat[MAXN];
struct scoef { int a, b, c; } coef[MAXN], D1, D2;
                      //A = y1 - y2; B = x2 - x1; C = x1 * y2 - x2 * y1
int x[MAXN];
int nr[MAXN];
struct punct2 { float x, y; } mid[MAXN][MAXN], P1, P2;
int did[MAXN][MAXN];
const int lg[MAXN] = {1,1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,256,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512,512};

punct tmp[MAXN];
latura temp[MAXN]; scoef temp2[MAXN];
void inline merge(int l, int r)
{
    if (l == r) return;
    int m = (l + r) >> 1, i, j, k, I, J;
    merge(l, m);
    merge(m + 1, r);
    for (i = k = I = l, j = J = m + 1; i <= m || j <= r; )
    {
        if (j > r || (i <= m && (pct[i].x < pct[j].x || (pct[i].x == pct[j].x && pct[i].y < pct[j].y))))
            tmp[k] = pct[i++];
        else
            tmp[k] = pct[j++];
        if (J > r || (I <= m && lat[I].a.x <= lat[J].a.x))
            temp2[k] = coef[I],
            temp[k++] = lat[I++];
        else
            temp2[k] = coef[J],
            temp[k++] = lat[J++];
    }
    for (k = l; k <= r; k++) pct[k] = tmp[k], coef[k] = temp2[k], lat[k] = temp[k];
}

punct2 tmp1[MAXN]; int tmp2[MAXN];
void inline mergelat(int l, int r, int K)
{
    if (l == r) return;
    int m = (l + r) >> 1, i, j, k;
    mergelat(l, m, K);
    mergelat(m + 1, r, K);
    for (i = k = l, j = m + 1; i <= m || j <= r; )
        if (j > r || (i <= m && (mid[K][i].x < mid[K][j].x || (mid[K][i].x == mid[K][j].x && mid[K][i].y < mid[K][j].y))))
            tmp1[k] = mid[K][i],
            tmp2[k++] = did[K][i++];
        else
            tmp1[k] = mid[K][j],
            tmp2[k++] = did[K][j++];
    for (k = l; k <= r; k++) mid[K][k] = tmp1[k], did[K][k] = tmp2[k];
}

void inline lineintersec(scoef P1, scoef P2, punct2 &x)
{
    int det = P2.a * P1.b - P1.a * P2.b;
    if (det == 0)
    {
        x.x = x.y = -1;
        return;
    }
    x.x = (float)(P2.b * P1.c - P1.b * P2.c) / det;
    x.y = (float)(P1.a * P2.c - P2.a * P1.c) / det;
}

int inline sign(int ID, int X, int Y)
{
    float x = coef[ID].a * X + coef[ID].b * Y + coef[ID].c;
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

int inline ispoint(int X, int Y)
{
    int i, step;
    for (i = 0, step = lg[n]; step; step >>= 1)
        if (i + step < n && (pct[i + step].x < X  || (pct[i + step].x == X && pct[i + step].y <= Y)))
            i += step;
    return pct[i].x == X && pct[i].y == Y;
}

int inline isin(int X, int Y)
{
    if (X < x[0] || X > x[x0]) return 0;
    if (ispoint(X, Y)) return 1;
    int poz, step, i;
    float a;
    for (poz = 0, step = lg[x0]; step; step >>= 1)
        if (poz + step < x0 && x[poz + step] < X)
            poz += step;
    for (i = 0, step = lg[nr[poz]]; step; step >>= 1)
        if (i + step < nr[poz] && (a = sign(did[poz][i + step], X, Y)) >= 0)
        {
            i += step;
            if (a == 0) return 1;
        }
    if (sign(did[poz][i + 1], X, Y) >= 0)
        i++;
    return i % 2;
}

void inline getcoef(int x)
{
    coef[x].a = lat[x].a.y - lat[x].b.y;
    coef[x].b = lat[x].b.x - lat[x].a.x;
    coef[x].c = lat[x].a.x * lat[x].b.y - lat[x].b.x * lat[x].a.y;
}

int main()
{
    freopen("poligon.in", "rt", stdin);
    freopen("poligon.out", "wt", stdout);
    scanf("%d %d", &n, &m);
    scanf("%d %d", &pct[0].x, &pct[0].y);
    for (i = 1; i < n; i++)
    {
        scanf("%d %d", &pct[i].x, &pct[i].y);
        if (pct[i - 1].x <= pct[i].x)
            lat[i - 1].a = pct[i - 1],
            lat[i - 1].b = pct[i];
        else
            lat[i - 1].a = pct[i],
            lat[i - 1].b = pct[i - 1];
        getcoef(i - 1);
    }
    if (pct[n - 1].x <= pct[0].x)
        lat[n - 1].a = pct[n - 1],
        lat[n - 1].b = pct[0];
    else
        lat[n - 1].a = pct[0],
        lat[n - 1].b = pct[n - 1];
    getcoef(n - 1);

    merge(0, n - 1);

    x[ x0 = 0 ] = pct[0].x;
    for (i = 1; i < n; i++)
        if (pct[i].x != pct[i - 1].x)
           x[ ++x0 ] = pct[i].x;
    D1.a = -1; D1.b = 0;
    D2.a = -1; D2.b = 0;
    for (i = 0; i < x0; i++)
    {
        D1.c = x[i]; D2.c = x[i + 1];
        nr[i] = 0;
        for (j = 0; j < n && lat[j].a.x <= x[i]; j++)
        {
            lineintersec(D1, coef[j], P1);
            if (lat[j].a.x > P1.x || P1.x > lat[j].b.x)
                continue;
            lineintersec(D2, coef[j], P2);
            if (lat[j].a.x > P2.x || P2.x > lat[j].b.x)
                continue;
            did[i][++nr[i]] = j;
            mid[i][nr[i]].x = (P1.x + P2.x) * 0.5;
            mid[i][nr[i]].y = (P1.y + P2.y) * 0.5;
        }
        if (nr[i] > 0)
            mergelat(1, nr[i], i);
    }
    for (; m; m--)
    {
        scanf("%d %d", &i, &j);
        if (isin(i, j)) NR++;
    }
    printf("%d\n", NR);
    return 0;
}