Cod sursa(job #575483)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 8 aprilie 2011 12:58:18
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#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;
}