Cod sursa(job #559376)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 17 martie 2011 19:53:56
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 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,sol;

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( !(p1<p2) ) swap(p1,p2);
    if( (p1.x <= x1 && x1<p2.x)||(p1.x<x2 && x2<=p2.x)||( x1<=p1.x && p2.x<=x2 ) )
    {

        if(p1.x == p2.x ) return; // nu bag verticale
        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;
}

inline int ver_vertical(int i){
    int l,r,m,k;
        l=1; r=N;
        while( l<=r ){
            m=l+(r-l)/2;
            if( A[ind[m]].x >= B[i].x ) k=m, r=m-1;
            else l=m+1;
        }
        for(; k+1<=N && A[ind[k]].x==B[i].x ; ++k )
            if( A[ind[k]+1].x==B[i].x )
            if( A[ind[k]].y <= B[i].y && B[i].y<=A[ind[k]+1].y ){
                sol++;
                return 1;
            }
    return 0;
}

int main(){
    int i,j,l,r,m,ceva,k;
    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){
        // verific dc apartine de vreo latura verticala
        if( ver_vertical(i) ) continue;

        // vad in ce banda e
        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 ){

                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;
}