Cod sursa(job #540830)

Utilizator indestructiblecont de teste indestructible Data 24 februarie 2011 14:48:50
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 805
#define LMAX 60005
#define pdd pair <double,double>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
struct pct{int a,b;};
pct A[NMAX];
int n,m,B[NMAX],r,x,y,rez,D[LMAX];
vector <pdd> C[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&A[i].a,&A[i].b);
		B[++r]=A[i].a;
	}
	A[n+1]=A[1];
}
bool comp(pdd x,pdd y)
{
	return (x.f+x.s)<(y.f+y.s);
}
void prepare()
{
	int i,j,poz=1,a,b,c,x3,x4;
	for (i=2; i<=r; i++)
		if (B[i]!=B[i-1])
			B[++poz]=B[i];
	r=poz;
	for (i=1; i<r; i++)
		for (j=B[i]; j<B[i+1]; j++)
			D[j]=i;
	double x1,y1,x2,y2,aux;
	for (i=1; i<r; i++)
	{
		for (j=1; j<=n; j++)
		{
			a=A[j].b-A[j+1].b;
			b=A[j+1].a-A[j].a;
			c=A[j].a*A[j+1].b-A[j+1].a*A[j].b;
			
			x3=A[j].a; x4=A[j+1].a;
			if (A[j+1].a<A[j].a)
				x3=A[j+1].a,x4=A[j].a;
			if (b && x3<=B[i] && B[i+1]<=x4)
			{
				x1=B[i]; x2=B[i+1];
				y1=(-c-a*x1)/b;
				y2=(-c-a*x2)/b;
				if (y1>y2)
					aux=y1,y1=y2,y2=aux;
				C[i].pb(mp(y1,y2));
			}
		}
	}
	for (i=1; i<r; i++)
		sort(C[i].begin(),C[i].end(),comp);
}
int semn(int where,pdd act)
{
	double a=act.f-act.s;
	double b=B[where+1]-B[where];
	double c=B[where]*act.s-B[where+1]*act.f;
	return (a*x+b*y+c)>=0;
}
int cb(int where)
{
	int i,step;
	for (step=1; step<=C[where].size(); step<<=1);
	for (i=-1; step; step>>=1)
		if (i+step<C[where].size() && semn(where,C[where][i+step]))
			i+=step;
	return i;
}
void solve()
{
	int i,poz,poz2;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		if (x<B[1] || x>B[r])
			continue ;
		if (x==B[1])
			poz=1;
		else
			if (x==B[r])
				poz=r-1;
			else
				poz=D[x];
		poz2=cb(poz)+1;
		if (poz2 & 1)
			rez++;
	}
}
int main()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	read();
	sort(B+1,B+r+1);
	prepare();
	solve();
	printf("%d\n",rez);
	return 0;
}