Cod sursa(job #491771)

Utilizator mgntMarius B mgnt Data 12 octombrie 2010 13:48:45
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 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];

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 operator<(const Edge&a,const Edge&b)
{	if((a.x1<=b.x1)&&(b.x1<=a.x2)){return 0<crp(a,b.x1,b.y1);}
	if((a.x1<=b.x2)&&(b.x2<=a.x2)){return 0<crp(a,b.x2,b.y2);}
	if((b.x1<=a.x1)&&(a.x1<=b.x2)){return 0>crp(b,a.x1,a.y1);}
	return 0>crp(b,a.x2,a.y2);
}

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 add_edges()
{	int i,j;
	for(i=0;K>i;++i)
	{L[i]=2;Edge e={0,maxz,-1,-1},f={0,maxz,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;
		if(x1>x2){t=x1;x1=x2;x2=t;t=y1;y1=y2;y2=t;}
		if(x1<x2)
		{	Edge e={x1,x2,y1,y2};
			for(j=0;K>j;++j){if((e.x1<=X[j])&&(X[j+1]<=e.x2)){S[j][L[j]++]=e;}}
		}
	}
	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 inside(int x, int y)
{	int a=0,b=K,m,i,s;
	long long int q;
	while(a<b){m=((a+b)/2);if(x<=X[m]){b=m;}else{a=m+1;}}
	i=b-1;if((X[i+1]==x)&&(2!=L[i+1])){++i;}
	a=0;b=L[i]-1;
	while(a<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+1;}
	}
	q=crp(S[i][a],x,y);if(0>q){--a;}
	s=((L[i]-1-a)-1);
	return (1==(s%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];}
	add_strips();
	add_edges();
	for(s=0;0<m;--m)
	{	is>>x>>y;
		if(inside(x,y)){++s;}
	}
	ofstream os("poligon.out");
	os<<s<<endl;
	return 0;
}