Cod sursa(job #560570)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 18 martie 2011 16:21:42
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Nmax 802
#define Mmax 60002
#define pb push_back
#define mp make_pair
#define pii pair< int,int >
#define LL long long
#define INF 2147000000
#define f first
#define s second
using namespace std;

struct punct{
    LL x,y;
    inline bool operator <( const punct &o ) const{
        return x<o.x;
    }
} A[Nmax],As[Nmax],B[Mmax],p0;

struct dreapta{
    LL a,b,c;
} Dr[Nmax];

vector< pii > banda[Nmax];
int size[Nmax],ind[Nmax],cine[Nmax];
int N,M,zero,sol,nrb;

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

inline int cmp2( pii a, pii b){
    return A[a.s].y+A[a.s+1].y < A[b.s].y+A[b.s+1].y;
}

inline int sus(int i, punct p ){
    LL q = Dr[i].a*p.x + Dr[i].b*p.y + Dr[i].c;
    if( q==0 ) zero=1;
    if( q>=0 ) return 1;
    return 0;
}

inline int deasupra(int b,int i){
    int l,r,m,ret=-1;
    l=0; r=size[b]-1;

    while(l<=r){
        m=l+(r-l)/2;
        if( sus( banda[b][m].s, B[i]) ) ret=m, l=m+1;
        else r=m-1;
    }

    return ret+1;
}

int main(){
    int i,j,l,r,m,ceva,k,ret;
    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];
    As[N+1]=A[N+1]=A[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<=M;++i) scanf("%d%d",&B[i].x,&B[i].y);

    sort(As+1,As+N+1);
    for(i=1;i<N;++i)
        if( As[i].x != As[i+1].x ){
            ++nrb; cine[nrb]=i;
            size[nrb]=0;

            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) ){
                    banda[nrb].pb(mp( i,j ) );
                    size[nrb]++;
                }

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

    for(i=1;i<=M;++i){

        l=1; r=nrb;
        while( l<=r ){
            m=l+(r-l)/2;
            if( As[cine[m]].x <= B[i].x && B[i].x <= As[cine[m]+1].x ){
                ret=m;
                l=m+1;
            } else
            if( B[i].x <= As[cine[m]].x ) r=m-1;
            else l=m+1;
        }

        zero=0;
        if( B[i].x==9 && B[i].y==21 ){
            sol++;
            sol--;
        }
        ceva = deasupra( ret,i);
        if( (ceva & 1) || zero ) sol++;
        zero=0;

    }

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