Cod sursa(job #594216)

Utilizator indestructiblecont de teste indestructible Data 6 iunie 2011 17:35:43
Problema Poligon Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define x first
#define y second
#define pii pair <int,int>
#define NMAX 805
#define pdd pair <double,double>
#define pb push_back
#define mp make_pair
using namespace std;
int n,m,B[NMAX],r=1,rez;
pii A[NMAX],D;
vector <pdd> C[NMAX];
vector <pii> vert[NMAX];
void read_prepare()
{
	scanf("%d%d",&n,&m);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&A[i].x,&A[i].y);
		B[i]=A[i].x;
	}
	A[n+1]=A[1];
	sort(B+1,B+n+1);
	for (i=2; i<=n; i++)
		if (B[i]!=B[i-1])
			B[++r]=B[i];
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
bool comp(pdd a,pdd b)
{
	return a.x+a.y<b.x+b.y;
}
int cb1(int val)
{
	int i,step;
	for (step=1; step<=r; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=r && B[i+step]<=val)
			i+=step;
	return i;
}
void prepare()
{
	int i,j,a,b,poz;
	double a1,b1,c1,y1,y2;
	for (i=1; i<r; i++)
	{
		for (j=1; j<=n; j++)
		{
			a=min(A[j].x,A[j+1].x); b=max(A[j].x,A[j+1].x);
			if (a<=B[i] && b>=B[i+1])
			{
				a1=A[j].y-A[j+1].y;
				b1=A[j+1].x-A[j].x;
				c1=(double)A[j].x*A[j+1].y-(double)A[j].y*A[j+1].x;
				y1=(-c1-a1*B[i])/b1, y2=(-c1-a1*B[i+1])/b1;
				C[i].pb(mp(y1,y2));
			}
		}
	}
	for (i=1; i<r; i++)
		sort(C[i].begin(),C[i].end(),comp);
	for (i=1; i<=n; i++)
		if (A[i].x==A[i+1].x)
		{
			poz=cb1(A[i].x);
			a=min(A[i].y,A[i+1].y); b=max(A[i].y,A[i+1].y);
			vert[poz].pb(mp(a,b));
		}
	for (i=1; i<=r; i++)
		sort(vert[i].begin(),vert[i].end());
}
inline int down(int x1,int x2,double y1,double y2)
{
	double a1=y1-y2;
	double b1=x2-x1;
	double c1=x1*y2-x2*y1;
	double yi=(-c1-a1*D.x)/b1;
	return yi<D.y;
}
int cb2(int poz)
{
	int i,step;
	for (step=1; step<=C[poz].size(); step<<=1);
	for (i=-1; step; step>>=1)
		if (i+step<C[poz].size() && down(B[poz],B[poz+1],C[poz][i+step].x,C[poz][i+step].y))
			i+=step;
	return ++i;
}
int cb3(int poz)
{
	int i,step;
	for (step=1; step<=vert[poz].size(); step<<=1);
	for (i=-1; step; step>>=1)
		if (i+step<vert[poz].size() && vert[poz][i+step].x<=D.y)
			i+=step;
	return i;
}
void solve()
{
	int i,poz1,poz2;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&D.x,&D.y);
		if (D.x<B[1])
			continue ;
		if (D.x>B[r])
			continue ;
		poz1=cb1(D.x);
		if (D.x==B[poz1])
		{
			poz2=cb3(poz1);
			if (vert[poz1].size()>0 && poz2!=-1)
				if (vert[poz1][poz2].y>=D.y)
				{
					rez++;
					continue ;
				}
		}
		poz2=cb2(poz1);
		if (poz2 & 1)
			rez++;
	}
}
int main()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	read_prepare();
	prepare();
	solve();
	printf("%d\n",rez);
	return 0;
}