Cod sursa(job #1199672)

Utilizator misinozzz zzz misino Data 20 iunie 2014 10:57:34
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define N 810
#define eps 1e-9

using namespace std;

ifstream f("poligon.in");
ofstream g("poligon.out");

int n,m,i,j,sol,poz,mini,maxi,banda,nrb,x,y,band[N],viz[60100];

struct punct{
    int x,y;
}p[N];

struct ecuatie{int a,b;
long long c;
    double n,m;
}ec[N];

vector<int>a[N];

inline bool cmp(int a,int b){
    double mij = (band[i] + band[i+1])/2.0;
    double y1 = mij * ec[a].m + ec[a].n;
    double y2 = mij * ec[b].m + ec[b].n;

    return y2 - y1 > eps;
}

inline int caut_binar(int x){

    int li,ls,mij;

    li = 0;
    ls = nrb + 1;

    while(li + 2 <= ls)
    {
        mij = (li + ls) >> 1;

        if(band[mij] <= x)
        {
            li = mij;
        }
        else
        {
            ls = mij;
        }
    }

    return li;
}

inline int caut_binar_poz(int x,int y){

    int li , ls , mij;
    long long det;

    sol = 0;
    li = -1;
    ls = a[banda].size();

    while(li + 2 <= ls){

        mij = (li + ls) >> 1;

        int poz = a[banda][mij];

        det = 1LL * ec[poz].a * x + 1LL * ec[poz].b * y + ec[poz].c;

        if(det == 0)
            return 1;

        if(det > 0LL)///Deasupra
            li = mij;
        else///Dedesupt
            ls = mij - 1;
    }

    ++ li;

    if(li & 1)
        return 1;

    return 0;
}

int main()
{
    f >> n >> m;

    for(i = 1 ; i <= n ; ++ i)
    {
        f >> p[i].x >> p[i].y;

        band[i] = p[i].x;
    }

    p[n + 1] = p[1];

    for( i = 1 ; i <= n ;++ i)///Calculez ecuatiile dreptelor
    {
        punct a,b;

        a = p[i];
        b = p[i+1];

        if(a.x > b.x)
            swap(a,b);

        ec[i].a = a.y - b.y;
        ec[i].b = b.x - a.x;
        ec[i].c = 1LL * a.x * b.y - 1LL * a.y * b.x;
        ec[i].m = -1.0 * ec[i].a / ec[i].b;
        ec[i].n = -1.0 * ec[i].c / ec[i].b;
    }

    sort(band + 1 , band + n + 1);///Fac benzile

    nrb = 1;

    for(i = 2 ; i <= n ; ++ i)
        if(band[i] != band[nrb])
            band[++ nrb] = band[i];

    for(i = 1 ; i <= nrb ; ++ i)/// Ducem dreapta paralela cu OY prin band[i]
    {
        for(j = 1 ; j <= n ; ++ j)
            if(min(p[j].x , p[j+1].x) <= band[i] && band[i] < max(p[j].x , p[j+1].x))
                /// Daca intersecteaza segmentul j
                a[i].push_back(j);

        sort(a[i].begin() , a[i].end() , cmp);
    }

    for(i = 1 ; i <= n ; ++ i)
    {
        if(max(p[i].x , p[i + 1].x) == band[nrb])
        {
            if(min(p[i].x , p[i + 1].x) == band[nrb])
            {
                mini = min(p[i].y, p[i + 1].y);
                maxi = max(p[i].y, p[i + 1].y);

                for(j = mini ; j <= maxi ; ++ j)
                    viz[j] = 1;
            }
            else
                if(p[i].x == band[nrb])
                    viz[p[i].y] = 1;
                else
                    viz[p[i+1].y] = 1;
        }
    }

    for( i = 1 ; i <= m ; ++ i)
    {
        f >> x >> y;

        if( x < band[1] || band[nrb] < x)
            continue;

        banda = caut_binar(x);///In ce banda se afla

        if(banda == nrb)
        {
            if(viz[y])
                ++ sol;

            continue;
        }

        sol += caut_binar_poz(x , y);
    }

    g << sol << '\n';

    return 0;
}