Cod sursa(job #1169196)

Utilizator misinozzz zzz misino Data 10 aprilie 2014 17:32:57
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.69 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define N 810
#define eps 0.000000001

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=1;
    ls=nrb-1;

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

        if(band[mij] <= x && x < band[mij+1])
            return mij;

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

    return nrb;
}

inline punct pmin(punct a,punct b){
    if(a.x < b.x)
        return a;
    return b;
}

inline punct pmax(punct a,punct b){
    if(a.x > b.x)
        return a;
    return b;
}

inline bool mai_sus(punct O,punct A, punct B){
    int x=(A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);

    return (x>=0)?1:0;
}

inline int caut_binar_poz(int x,int y){

    int li,ls,mij;
    long long det;

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

    while(li <= ls){

        mij=(li+ls)>>1;

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

        if(det == 0)
            return 1;
        if(det > 0LL)
            li=mij+1;
        else
            ls=mij-1;

    }
    if(li == a[banda].size())
        return 0;
    if(ls == -1)
        return 0;
    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;
    band[nrb]=band[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(p[i].x == p[i+1].x)
            {
                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(band[1] > x || 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;
}