Cod sursa(job #508008)

Utilizator mgntMarius B mgnt Data 7 decembrie 2010 12:20:23
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <algorithm>
using namespace std;

int const maxz=60000,maxn=800;
struct Edge{int x1,x2,y1,y2;} S[2+maxn][2+maxn],St[2+maxn];
int Z[maxn][2],X[2+maxn],L[2+maxn],N,K,O[2+maxn];
double M[2+maxn];

long long int crp(const 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,p=x1*y2-x2*y1;
	return p;
}

bool swo(int i,int j){return M[i]<M[j];}

void add_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 sort_edges(int j)
{	int i;
	for(i=1;L[j]>i;++i){O[i]=i;}
	double x=(X[j]+X[j+1])/2.0;
	double tg,dx;
	for(i=1;L[j]>i;++i)
	{	tg=((double)(S[j][i].y2-S[j][i].y1))/
			((double)(S[j][i].x2-S[j][i].x1));
		dx=(x-S[j][i].x1);
		M[i]=S[j][i].y1+dx*tg;
	}
	make_heap(O+1,O+L[j],swo);
	sort_heap(O+1,O+L[j],swo);
	for(i=1;L[j]>i;++i){St[i]=S[j][O[i]];}
	for(i=1;L[j]>i;++i){S[j][i]=St[i];}
}

void add_edges()
{	int i,j;
	for(j=0;K>j;++j)
	{	L[j]=0;Edge e={-1,maxz+1,-1,-1};S[j][L[j]++]=e;
		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;
			if(x1>x2){t=x1;x1=x2;x2=t;t=y1;y1=y2;y2=t;}
			if((x1<x2)&&(x1<=X[j])&&(X[1+j]<=x2))
			{Edge e={x1,x2,y1,y2};S[j][L[j]++]=e;}
		}
		sort_edges(j);
		Edge f={-1,maxz+1,maxz+1,maxz+1};S[j][L[j]++]=f;
	}
}

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

bool inside(int x, int y)
{	int a=0,b=K,m,i;
	while((a+1)<b){m=((a+b)/2);if(x<=X[m]){b=m;}else{a=m;}}
	i=a;if(inside(i,x,y)){return true;}
	++i;if((K>i)&&(X[i]==x)&&inside(i,x,y)){return true;}
	return false;
}

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