Cod sursa(job #559273)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 17 martie 2011 18:55:42
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Nmax 802
#define Mmax 60002
#define pb push_back
#define mp make_pair
#define pii LL
#define INF 2147000000
#define LL long long
using namespace std;

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

vector< pii > banda[Nmax];
int sz[Nmax],ind[Nmax];
int N,M,zero;

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 cmpA(int i,int j){
    return (A[i].x < A[j].x || (A[i].x==A[j].x && A[i].y<A[j].y) );
}
inline int cmp( int i,int j){
    return ( A[i].y+A[i+1].y < A[j].y+A[j+1].y );
}

inline void intersect(LL x1,LL x2,punct p1,punct p2,int i,int j){
    if( Minim(p1.x,p2.x) <=x1 && x2 <= Maxim(p1.x,p2.x) ){
        banda[i].pb( j );
        sz[i]++;
    }
}

inline int semn(punct p0,punct p1,punct p2){
 if( !(p0<p1) ) swap(p0,p1);
 if(p0.x*p1.y+p1.x*p2.y+p2.x*p0.y -p0.y*p1.x-p1.y*p2.x-p2.y*p0.x == 0 ) zero=1;
 if( (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y) <= 0 ) return 0;
 return 1;
}

inline int in_banda(int i, punct p){
    int l,r,m,ret=-1;

    l=0; r=sz[i]-1;
    while( l<=r ){
        m=l+(r-l)/2;
        if( semn( A[banda[i][m]],A[banda[i][m]+1],p )  )ret=m, l=m+1;
        else r=m-1;
    }
    return ret+1;
}

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

    sort(ind+1,ind+N+1,cmpA);
    A[0]=A[N];
    A[N+1]=A[1];

    for(i=1;i<N;++i){
      //  if( A[ind[i]].x == A[ind[i+1]].x ) continue;
        for(j=1;j<=N;++j)
            intersect(A[ind[i]].x,A[ind[i+1]].x,A[j],A[j+1],i,j);
        sort(banda[i].begin(), banda[i].end(), cmp );
    }

    for(i=1;i<=M;++i){
        l=1; r=N-1;
        while( l<=r ){
            m=l+(r-l)/2;

            if( A[ind[m]].x <= B[i].x && B[i].x <= A[ind[m+1]].x && A[ind[m]].x!=A[ind[m+1]].x){
                zero=0;
                ceva=in_banda(m,B[i]);
                if( (ceva & 1) || zero ) sol++;
                break;
            }
            if( B[i].x <= A[ind[m]].x ) r=m-1;
            else l=m+1;
        }
        l=1;
    }

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