Cod sursa(job #1096209)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 1 februarie 2014 18:20:44
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define NMax 810

using namespace std;

ifstream f ("poligon.in");
int nowbanda;
int n, m;
int ans;
int A[NMax], B[NMax];
long long C[NMax];
struct punct
{
    int x, y;
    punct(){}
    punct(const int x, const int y)
    {
        this -> x = x;
        this -> y = y;
    }
};
punct P[NMax];
int banda[NMax], nbanda, auxbanda[NMax], nauxbanda;
vector <int> v[NMax];
bool visited[NMax];

void Read()
{
    f>>n>>m;
    for (int i = 1; i<=n ;++i)
    {
        f>>P[i].x>>P[i].y;
        auxbanda[++nauxbanda] = P[i].x;
    }
    P[n+1] = P[1];
}

inline bool cmp(const int &ind1, const int &ind2)
{
    double mij = 1.0 * (banda[nowbanda] + banda[nowbanda+1]) / 2;
    int ymij1 = (- 1.0*C[ind1] - A[ind1] * mij) / B[ind1];
    int ymij2 = (- 1.0*C[ind2] - A[ind2] * mij) / B[ind2];
    return ymij1 < ymij2;
}

inline int GetBanda(const int x)
{
    int st = 1, dr = nbanda - 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 nbanda;
}

inline int InPoligon(const int x, const int y)
{
    if (x < banda[1] || x > banda[nbanda])
        return 0;
    int now = GetBanda(x);
    if (now == nbanda)
    {
        if (visited[y])
            return 1;
        return 0;
    }
    int st = 0, dr = v[now].size() - 1, mij;
    while (st <= dr)
    {
        mij = (st+dr)>>1;
		int ind = v[now][mij];
        long long det = 1LL*A[ind] * x + 1LL*B[ind]*y + C[ind];
        if (det == 0)
            return 1;
        if (det < 0LL) // e deasupra
            st = mij+1;
        else
            dr = mij-1;
    }
    if (st == v[now].size())
        return 0;
    if (dr == -1)
        return 0;
    if ((st & 1) == 1)
        return 1;
    return 0;

}

void Solve()
{
    sort(auxbanda + 1, auxbanda + nauxbanda + 1);
    banda[++nbanda] = auxbanda[1];
    for (int i = 2; i<=nauxbanda; ++i)
        if (auxbanda[i] != banda[nbanda])
            banda[++nbanda] = auxbanda[i];
    for (int i = 1; i<=n; ++i)
    {
        A[i] = P[i].y - P[i+1].y;
        B[i] = P[i+1].x - P[i].x;
        C[i] = 1LL * P[i].x * P[i+1].y - 1LL * P[i+1].x * P[i].y;
    }
    for (int i = 1; i < nbanda; ++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 j = 1; j<=n; ++j)
        if (max(P[j].x, P[j+1].x) == banda[nbanda])
        {
            if (min(P[j].x, P[j+1].x) == banda[nbanda])
            {
                int inflim = min(P[j].y, P[j+1].y), suplim = max(P[j].y, P[j+1].y);
                for (int i = inflim; i <= suplim; ++i)
                    visited[i] = true;
            }
            else if (P[j].x == banda[nbanda])
                visited[P[j].y] = true;
            else
                visited[P[j+1].y] = true;
        }
    while (m--)
    {
        int x, y; f>>x>>y;
        ans += InPoligon(x, y);
    }
    ofstream g("poligon.out");
    g<<ans<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}