Cod sursa(job #491294)

Utilizator mgntMarius B mgnt Data 10 octombrie 2010 20:37:14
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <algorithm>
using namespace std;
int const maxz=60000;
int const maxn=800;
struct Edge{int x1,x2,y1,y2;};
int Z[maxn][2],X[maxn+2],N,K;Edge S[2+maxn][2+maxn];int L[maxn];

bool operator<(const Edge&a,const Edge&b)
{	int e=a.y1,f=a.y2,g=b.y1,h=b.y2;
	if(e>f){f=e;}if(g<h){g=h;}
	return (f<g);
}

void set_vertical_strips()
{	int i,j;
	X[0]=-1;for(i=0;N>i;++i){X[1+i]=Z[i][0];}X[1+N]=maxz+1;
	make_heap(X,X+N+2);
	sort_heap(X,X+N+2);
	for(i=1,j=0;N+2>i;++i)
	{if(X[j]!=X[i]){++j;if(j!=i){X[j]=X[i];}}}K=j;
}

void add_cutting_edges()
{	int i;
	for(i=0;K>i;++i)
	{	L[i]=2;Edge e={X[i],X[i+1],-1,-1},f={X[i],X[i+1],maxz+1,maxz+1};
		S[i][0]=e;S[i][1]=f;
	}
	for(i=0;N>i;++i)
	{	int x1=Z[i][0],y1=Z[i][1],x2=Z[(1+i)%N][0],y2=Z[(1+i)%N][1],t,u,w;
		if(x1>x2){t=x1;x1=x2;x2=t;t=y1;y1=y2;y2=t;}
		Edge e={x1,x2,y1,y2};
		u=0;while((K>=u)&&(X[u]<x1)){++u;}
		w=1+u;while((K>=w)&&(X[w]<=x2)){S[w-1][L[w-1]++]=e;++w;}
	}
	for(i=0;K>i;++i)
	{	make_heap(&S[i][0],&S[i][L[i]]);
		sort_heap(&S[i][0],&S[i][L[i]]);
	}
}

bool above(Edge & e,int x,int y)
{	long long int x1=e.x2-e.x1,y1=e.y2-e.y1,x2=x-e.x1,y2=y-e.y1,pr=x1*y2-x2*y1;
	return (0>pr);
}

bool inside(int x, int y)
{	int a=0,b=K,m,i;
	while(a<b){m=((a+b)/2);if(x<=X[m]){b=m;}else{a=m+1;}}i=a-1;a=0;b=L[i]-1;
	while(a<b){m=(a+b)/2;if(above(S[i][m],x,y)){b=m;}else{a=m+1;}}
	return (0==((L[i]-a)%2));;
}

int main()
{	ifstream is("poligon.in");int m;
	is>>N>>m;int i,s,x,y;
	for(i=0;N>i;++i){is>>Z[i][0]>>Z[i][1];}
	set_vertical_strips();
	add_cutting_edges();
	for(s=0;0<m;--m)
	{	is>>x>>y;
		if(inside(x,y)){++s;}
	}
	ofstream os("poligon.out");
	os<<s<<endl;
	return 0;
}