Pagini recente » Cod sursa (job #1993523) | Cod sursa (job #2460884) | Cod sursa (job #1989436) | Cod sursa (job #1118608) | Cod sursa (job #1721959)
#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;
}