Cod sursa(job #1722676)

Utilizator akaprosAna Kapros akapros Data 28 iunie 2016 17:55:09
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
#define maxN 805
using namespace std;
int ans, n, m, k, b[maxN], A[maxN], B[maxN], C[maxN];
int act;
bool ok;
double sa[maxN], sb[maxN];
vector < int > V[maxN];

struct coord
{
    int x, y;
} v[maxN];

bool cmp(int x, int y)
{
    return (sa[x] * (b[act] + b[act + 1]) + sb[x] * 2) < (sa[y] * (b[act] + b[act + 1]) + sb[y] * 2);
}
bool Ok(int i, int x, int y)
{
    if (A[i] * x + B[i] * y + C[i] == 0)
        ok = 1;
    return 1.00 * y >= (sa[i] * x + sb[i]);
}
int bs(int x)
{
    int i = 0, p = 1 << 9;
    while (p)
    {
        if (i + p <= k && b[i + p] < x)
            i += p;
        p >>= 1;
    }
    return i;
}
int Bs(int q, int x, int y)
{
    int i = 0, p = 1 << 9, len = V[q].size();
    while (p)
    {
        if (i + p <= len && Ok(V[q][i + p - 1], x, y))
            i += p;
        p >>= 1;
    }
    return i;
}
void read()
{
    int i;
    freopen("poligon.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &v[i].x, &v[i].y);
        b[i] = v[i].x;
    }
    v[n + 1] = v[1];
}
void solve()
{
    int i, j;
    sort(b + 1, b + n + 1);
    for (i = 1; i <= n; ++ i)
    {
        A[i] = v[i + 1].y - v[i].y;
        B[i] = v[i].x - v[i + 1].x;
        C[i] = -v[i].x * v[i + 1].y + v[i + 1].x * v[i].y;
        sa[i] = -1.0 * A[i] / B[i];
        sb[i] = -1.0 * C[i] / B[i];
        if (b[i] != b[i - 1] || i == 1)
            b[++ k] = v[i].x;
    }
    b[k + 1] = 0;
    for (i = 1; i <= k; ++ i)
    {
        act = i;
        for (j = 1; j <= n; ++ j)
            if ((v[j].x > b[i] && v[j + 1].x <= b[i]) || (v[j].x <= b[i] && v[j + 1].x > b[i]))
                V[i].push_back(j);
        sort(V[i].begin(), V[i].end(), cmp);
    }

    int x, y, p, q;
    while (m --)
    {
        scanf("%d %d", &x, &y);
        if (x < b[1] || x > b[k])
            continue;
        ok = 0;
        p = bs(x);
        q = Bs(p, x, y);
        if (q % 2 || ok)
            ++ ans;
    }
}
void write()
{
    freopen("poligon.out", "w", stdout);
    printf("%d\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}