Cod sursa(job #597945)

Utilizator drywaterLazar Vlad drywater Data 24 iunie 2011 01:06:16
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.11 kb
#include <fstream>
#include <algorithm>
#define fi first
#define se second
#define LL long long
using namespace std;
ifstream f("poligon.in");
ofstream o("poligon.out");
struct dreapta{int a; int b; int c;};
dreapta a[801];
struct banda{pair<double,int> v[801];};
banda bv[801];
int n,m,v[801][2],x,y,i,j,xu[801],nr,k,sol,sol2,s,xf[801],p,pe_lat;
LL u;
inline int mini(int a,int b)
{
    if (a<b) return a;
    return b;
}
inline int maxi(int a,int b)
{
    if (a<b) return b;
    return a;
}
int main(void)
{
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>v[i][0]>>v[i][1];
        if (i>1)
        {
            a[i-1].a=v[i-1][1]-v[i][1];
            a[i-1].b=v[i][0]-v[i-1][0];
            a[i-1].c=v[i-1][0]*v[i][1]-v[i-1][1]*v[i][0];
            if (a[i-1].b<0) {a[i-1].a*=(-1); a[i-1].b*=(-1); a[i-1].c*=(-1);}
        }
        xu[i]=v[i][0];
    }
    v[i][0]=v[1][0];
    v[i][1]=v[1][1];
    a[i-1].a=v[i-1][1]-v[i][1];
    a[i-1].b=v[i][0]-v[i-1][0];
    a[i-1].c=v[i-1][0]*v[i][1]-v[i-1][1]*v[i][0];
    if (a[i-1].b<0)
    {a[i-1].a*=(-1); a[i-1].b*=(-1); a[i-1].c*=(-1);}
    sort(xu+1,xu+n+1);
    p=0;
    for (i=1;i<=n;i++)
    {
        if (i==1 || xu[i]!=xu[i-1])
            xf[++p]=xu[i];
    }
    for (i=1;i<p;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (mini(v[j][0],v[j+1][0])<=xf[i] && maxi(v[j+1][0],v[j][0])>=xf[i+1])
            {
                double aa,b,c,x,y;
                aa=a[j].a;
                b=a[j].b;
                c=a[j].c;
                x=xf[i]+xf[i+1];
                x/=2;
                y=(-1)*(aa*x+c)/b;
                bv[i].v[++bv[i].v[0].se]=make_pair(y,j);

            }
        }
        sort(bv[i].v+1,bv[i].v+bv[i].v[0].se+1);
    }
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        if (x<xf[1] || x>xf[p]) continue;
        k=1;
        while (k<=p) k*=2;
        k/=2;
        sol=0;
        while (k>0)
        {
            if (sol+k<p && x<xf[sol+k]) sol+=k;
            k/=2;
        }
        sol++;
        sol2=0;
        k=1;
        while (k<=bv[sol].v[0].se) k*=2;
        k/=2;
        while (k>0)
        {
            s=bv[sol].v[sol2+k].se;
            u=a[s].a*x+a[s].b*y+a[s].c;
            if (u==0) pe_lat=1;

            if (sol2+k<=bv[sol].v[0].se && u<0) sol2+=k;
            k/=2;
        }
        if (sol2%2!=0 || pe_lat) nr++;
        pe_lat=0;
    }
    o<<nr<<"\n";
    return 0;
}/*
#include <stdio.h>
#include <algorithm>
#include <vector>
#define Nmax 802
#define Mmax 60002
#define pii pair<double,int>
#define f first
#define s second
#define LL long long
#define pb push_back
#define mp make_pair
#define INF 2147000000
using namespace std;

struct punct {
    int x,y;
    inline bool operator < ( const punct &o ) const{
        return x==o.x ? y<o.y : x<o.x;
    }
} A[Nmax],As[Nmax],p;
struct dreapta{
    int a,b,c;
} Dr[Nmax];

vector< pii > banda[Nmax];
int cine[Nmax];
int N,M,nrb,pe_lat;

inline int Minim(int x,int y){ return x<y ? x:y; }
inline int Maxim(int x,int y){ return x>y ? x:y; }

inline int find_banda(punct p){
    int l=1, r=nrb,m,ret=-1;
    while( l<=r ){
        m=l+(r-l)/2;
        if( As[cine[m]].x <= p.x && p.x<=As[cine[m]+1].x ) {
            ret=m;
            l=m+1;
        }else
        if( p.x <= As[cine[m]].x ) r=m-1;
        else l=m+1;
    }
    return ret;
}

inline int deasupra(int j,punct p){
    LL u = Dr[j].a*p.x + Dr[j].b*p.y + Dr[j].c;
    if( u==0 ) pe_lat=1;
    if( u>0 ) return 1;
    return 0;
}

inline int check(int b, punct p){
    int l,m,r,ret=-1;
    l=0; r=banda[b].size()-1;
    while( l<=r ){
        m=l+(r-l)/2;
        if( deasupra( banda[b][m].s, p ) ) ret=m,l=m+1;
        else r=m-1;
    }
    return ret+1;
}

int main(){
    int i,j,sol,bb; double a,b,c,x,y;
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;++i)
        scanf("%d%d",&A[i].x,&A[i].y),As[i]=A[i];
    A[N+1]=A[1];
    sort(As+1,As+N+1);

    for(i=1;i<=N;++i){
        Dr[i].a=A[i].y-A[i+1].y;
        Dr[i].b=A[i+1].x-A[i].x;
        Dr[i].c=A[i].x*A[i+1].y - A[i+1].x*A[i].y;
        if( Dr[i].b<0 ) Dr[i].a*=-1,Dr[i].b*=-1,Dr[i].c*=-1;
    }

    for(i=1;i<N;++i) // pentru fiecare banda
        if( As[i].x != As[i+1].x ){
            ++nrb; cine[nrb]=i;

            for(j=1;j<=N;++j)
                if( Minim(A[j].x,A[j+1].x)<= As[i].x && As[i+1].x<=Maxim(A[j].x,A[j+1].x) ){
                    a=Dr[j].a; b=Dr[j].b; c=Dr[j].c;
                    x=(As[i].x+As[i+1].x)/2;
                    y=(-1)*(c+a*x)/b;

                    banda[nrb].pb(mp(y,j));
                }

            if( banda[nrb].empty() ) nrb--;
            else sort(banda[nrb].begin(),banda[nrb].end());
        }

    sol=0;
    for(i=1;i<=M;++i){
        scanf("%d%d",&p.x,&p.y);
        bb=find_banda(p);
        if( bb==-1 ) continue;

        pe_lat=0;
        if( (check(bb,p)&1) || pe_lat ) sol++;
    }

    printf("%d\n",sol);
    fclose(stdin); fclose(stdout);
    return 0;
}*/