Cod sursa(job #1721959)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 26 iunie 2016 21:04:22
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<cstdio>
#include<algorithm>
#define MAXN 810
using namespace std;
pair<int,int> v[MAXN];
vector<int> strip[MAXN];
int x[MAXN],i;
int a[MAXN],b[MAXN],c[MAXN],colinear;
double a0[MAXN],b0[MAXN];
bool compare(int a,int b){
    return (a0[a]*(x[i]+x[i+1])+2*b0[a]<a0[b]*(x[i]+x[i+1])+2*b0[b]);
}
bool Check(int index,int x0,int y0){
    if(a[index]*x0+b[index]*y0+c[index]==0)
        colinear=1;
    return (y0>=a0[index]*x0+b0[index]);
}
int main(){
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);
    int n,m,j,nx=0,q,x0,y0,answer=0,step;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d%d",&v[i].first,&v[i].second);
        x[i]=v[i].first;
    }
    v[n+1]=v[1];
    sort(x+1,x+n+1);
    x[0]=-1;
    for(i=1;i<=n;i++)
        if(x[i]!=x[i-1]){
            nx++;
            x[nx]=x[i];
        }
    x[nx+1]=0;
    for(i=1;i<=n;i++){
        a[i]=v[i+1].second-v[i].second;
        b[i]=v[i].first-v[i+1].first;
        c[i]=-(a[i]*v[i].first+b[i]*v[i].second);
        a0[i]=-1.0*a[i]/b[i];
        b0[i]=-1.0*c[i]/b[i];
    }
    for(i=1;i<=nx;i++){
        for(j=1;j<=n;j++)
            if((x[i]>=v[j].first&&x[i]<v[j+1].first)||(x[i]>=v[j+1].first&&x[i]<v[j].first))
                strip[i].push_back(j);
        sort(strip[i].begin(),strip[i].end(),compare);
    }
    for(q=1;q<=m;q++){
        scanf("%d%d",&x0,&y0);
        if(x0<x[1]||x0>x[nx])
            continue;
        i=j=colinear=0;
        for(step=1024;step>0;step/=2)
            if(i+step<=nx&&x[i+step]<x0)
                i+=step;
        for(step=1024;step>0;step/=2)
            if(j+step<=strip[i].size()&&Check(strip[i][j+step-1],x0,y0))
                j+=step;
        if(j%2==1||colinear==1)
            answer++;
    }
    printf("%d",answer);
    return 0;
}