Cod sursa(job #1140422)

Utilizator Ionut228Ionut Calofir Ionut228 Data 11 martie 2014 23:23:44
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.14 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

const double eps = 1e-9;

int N, M;
int sol, X, Y;
int banda[801], nrbanda, nowbanda;
double ecm[801], ecn[801];
vector<int> V[801];
bool viz[60001];

struct puncte
{
    int x, y;
};
puncte P[801];

struct dreapta
{
    int a, b, c;
};
dreapta Ec[801];

double gety(int now, int xnow)
{
    return ecm[now] * xnow / 2.0 + ecn[now];
}

bool cmp(int nr1, int nr2)
{
    int xmid = banda[nowbanda] + banda[nowbanda + 1];
    double y1 = gety(nr1, xmid);
    double y2 = gety(nr2, xmid);

    return y2 - y1 > eps;
}

int GetBanda()
{
    /*
    int l = 0, r = nrbanda + 1;

    while (r - l > 1)
    {
        int mid = (l + r) / 2;

        if (banda[mid] <= X && X < banda[mid + 1])
            return mid;
        if (banda[mid] <= X)
            l = mid;
        else
            r = mid;
    }
    return l;
    */
    int st = 1, dr = nrbanda - 1, mij;

    while (st <= dr)
    {
        mij = (st+dr) >> 1;
        if (banda[mij] <= X && X < banda[mij+1])
            return mij;
        if (banda[mij] <= X)
            st = mij+1;
        else
            dr = mij-1;
    }
    return nrbanda;
}

int solve()
{
    if (X < banda[1] || X > banda[nrbanda])
        return 0;
    int nowbanda = GetBanda();

    if (nowbanda == nrbanda)
    {
        if (viz[Y])
            return 1;
        return 0;
    }

/*
    int l = -1, r = V[nowbanda].size();

    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        int now = V[nowbanda][mid];
        int det = Ec[now].a * X + Ec[now].b * Y + Ec[now].c;

        if (det == 0)
            return 1;
        if (det <= 0)
            l = mid;
        else
            r = mid;
    }
    if (l == V[nowbanda].size())
        return 0;
    if (r == -1)
        return 0;
    if (l & 1)
        return 1;
    return 0;
    */
    int st = 0, dr = V[nowbanda].size() - 1, mij;

    while (st <= dr)
    {
        mij = (st+dr)>>1;
        int ind = V[nowbanda][mij];
        long long det = 1LL*Ec[ind].a * X + 1LL*Ec[ind].b*Y + Ec[ind].c;
        if (det == 0)
            return 1;
        if (det > 0LL) // e deasupra
            st = mij+1;
        else
            dr = mij-1;
    }
    if (st == V[nowbanda].size())
        return 0;
    if (dr == -1)
        return 0;
    if ((st & 1) == 1)
        return 1;
    return 0;
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; ++i)
    {
        fin >> P[i].x >> P[i].y;
        banda[i] = P[i].x;
    }
    P[N + 1] = P[1];

    sort(banda + 1, banda + N + 1);
    banda[++nrbanda] = banda[1];
    for (int i = 2; i <= N; ++i)
        if (banda[i] != banda[nrbanda])
            banda[++nrbanda] = banda[i];

    for (int i = 1; i <= N; ++i)
    {
        Ec[i].a = P[i + 1].y - P[i].y;
        Ec[i].b = P[i].x - P[i + 1].x;
        Ec[i].c = P[i + 1].x * P[i].y - P[i].x * P[i + 1].y;
        ecm[i] = -1.0 * Ec[i].a / Ec[i].b;
        ecn[i] = -1.0 * Ec[i].c / Ec[i].b;
    }

    for (int i = 1; i <= nrbanda; ++i)
    {
        for (int j = 1; j <= N; ++j)
            if (min(P[j].x, P[j + 1].x) <= banda[i] && banda[i] < max(P[j].x, P[j + 1].x))
                V[i].push_back(j);
        nowbanda = i;
        sort(V[i].begin(), V[i].end(), cmp);
    }

    for (int i = 1; i <= N; ++i)
    {
        if (max(P[i].x, P[i + 1].x) == banda[nrbanda])
        {
            if (min(P[i].x, P[i + 1].x) == banda[nrbanda])
            {
                int liminf = min(P[i].y, P[i + 1].y);
                int limsup = max(P[i].y, P[i + 1].y);

                for (int j = liminf; j <= limsup; ++j)
                    viz[j] = true;
            }
            else if (P[i].x == banda[nrbanda])
                viz[P[i].y] = true;
            else
                viz[P[i + 1].y] = true;
        }
    }

    while (M)
    {
        fin >> X >> Y;
        sol += solve();

        --M;
    }

    fout << sol << '\n';

    fin.close();
    fout.close();
    return 0;
}