Cod sursa(job #1140239)

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

using namespace std;

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

int N, M;
int curBucket, onLine;
int bandanow, banda, lowerpoints;
int sol, nrdrepte;
double ecm[801], ecn[801];
int D[801];
vector<int> V[801];

struct puncte
{
    int x, y;
};
puncte A[801], B[801], punct;

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

bool cmp(puncte a, puncte b)
{
    return (a.x < b.x || (a.x == b.x && a.y < b.y));
}

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

bool sortnow(int nr1, int nr2)
{
    int xnow = D[bandanow] + D[bandanow + 1];
    double y1 = gety(nr1, xnow);
    double y2 = gety(nr2, xnow);

    return y1 < y2;
}

/*
int det(puncte pctA, puncte pctB, puncte pctC)
{
    if (pctA.x < pctB.x)
        swap(pctA, pctB);
    return pctA.x * pctB.y + pctB.x * pctC.y + pctC.x * pctA.y - (pctC.x * pctB.y + pctA.x * pctC.y + pctB.x * pctA.y);
}
*/
bool higher(puncte P, int now)
{
    if (Ec[now].a * P.x + Ec[now].b * P.y + Ec[now].c == 0) onLine = 1;
    return (P.y >= gety(now, P.x));
}

int cb1()
{
    int l = 0, r = nrdrepte + 1;

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

        if (D[mid] <= punct.x)
            l = mid;
        else
            r = mid;
    }
    return l;
}

int cb2()
{
    int l = -1, r = V[banda].size();

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

        if (higher(punct, V[banda][mid]))
            l = mid;
        else
            r = mid;
    }
    return l;
}

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

    sort(B + 1, B + N + 1, cmp);
    D[++nrdrepte] = B[1].x;
    for (int i = 2; i <= N; ++i)
        if (B[i - 1].x != B[i].x)
            D[++nrdrepte] = B[i].x;

    for (int i = 1; i <= N; ++i)
    {
        //Ec[i].a = A[i + 1].y - A[i].y;
        //Ec[i].b = A[i].x - A[i + 1].x;
        //Ec[i].c = A[i + 1].x * A[i].y - A[i].x * A[i + 1].y;
        Ec[i].a = A[i].y - A[i + 1].y;
        Ec[i].b = A[i + 1].x - A[i].x;
        Ec[i].c = A[i].x * A[i + 1].y - A[i + 1].x * A[i].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 < nrdrepte; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (min(A[j].x, A[j + 1].x) <= D[i] && D[i] < max(A[j].x, A[j + 1].x))
                V[i].push_back(j);
        }
        bandanow = i;
        sort(V[i].begin(), V[i].end(), sortnow);
    }

    while (M)
    {
        fin >> punct.x >> punct.y;
        if (punct.x < D[1] || punct.x > D[nrdrepte]) continue;

        curBucket = onLine = 0;
        for (int step = 10; step >= 0; --step)
            if (curBucket + (1 << step) <= nrdrepte && D[curBucket + (1 << step)] < punct.x)
                curBucket += (1 << step);
        int j = 0;
        for (int step = 10; step >= 0; --step)
            if (j + (1 << step) <= V[curBucket].size() && higher(punct, V[curBucket][j + (1 << step) - 1]))
                j += (1 << step);
        if (j % 2 == 1 || onLine == 1)
            ++sol;

        --M;
    }

    fout << sol << '\n';

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