Cod sursa(job #552755)

Utilizator ilincaSorescu Ilinca ilinca Data 12 martie 2011 19:49:12
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.75 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define nmax 815
#define y first
#define x second
#define y1 first
#define y2 second
#define mp make_pair

using namespace std;

typedef pair <int, int> ii;
typedef pair <double, int> interval;

int n, m, nintr, nrsegm [nmax];
ii p [nmax], p2 [nmax];
ii intr [nmax];
interval segm [nmax] [nmax];

void scan ()
{
	int i;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= n; ++i)
	{
		scanf ("%d%d", &p [i].x, &p [i].y);
		p2 [i]=p [i];
	}
}

double xmijloc (int p1, int p2, int k)
{
	double mx, p1x, p2x, p1y, p2y;
	int aux;
	if (p [p1].y > p [p2].y)
	{
		aux=p1;
		p1=p2;
		p2=aux;
	}
	p1y=p [p1].y;
	p2y=p [p2].y;
	if (p1y < intr [k].y1)
		p1y=intr [k].y1;
	if (p2y > intr [k].y2)
		p2y=intr [k].y2;
	long long a=p [p1].y-p [p2].y, b=p [p2].x-p [p1].x, c=(long long)p [p1].x*p [p2].y - (long long)p [p1].y*p [p2].x;
	p1x=(double)(-b*p1y-c)/a;
	p2x=(double)(-b*p2y-c)/a;
	mx=(p1x + p2x)/2;
	return mx;
}

void bucatele ()
{
	int i, j;
	ii a1, a2, aux;
	sort (p2+1, p2+1+n);
	p [n+1]=p [1];
	i=2;
	for (; i < n && p2 [i].y == p2 [i-1].y; ++i);
	--i;
	for (; i < n; ++i)
	{
		j=i+1;
		while (j < n && p2 [j+1].y == p2 [j].y)
			++j;
		intr [++nintr]=ii (p2 [i].y, p2 [j].y);
	//	fprintf (stderr, "%d %d\n", intr [nintr].y1, intr [nintr].y2);
		i=j-1;
	}
	for (i=1; i <= nintr; ++i)
	{
		for (j=1; j <= n; ++j)
		{
			a1=p [j];
			a2=p [j+1];
			if ((a1.y > a2.y) || (a1.y == a2.y && a1.x > a2.x))
			{
				aux=a1;
				a1=a2;
				a2=aux;
			}
			if (a1.y >= intr [i].y2) continue;
			if (a2.y <= intr [i].y1) continue;
			segm [i] [++nrsegm [i]]= (mp (xmijloc (j, j+1, i), j));
		//	fprintf (stderr, "%d %d\n", i, j);
		}
		sort (segm [i]+1, segm [i]+1+nrsegm [i]);
	}
}

bool exista (ii punct)
{
	int s=1<<10, i;
	for (i=0; s; s >>= 1)
	{
		if (n < i+s) continue;
		if (punct.y < p2 [i+s].y) continue;
		if (punct.y == p2 [i+s].y && punct.x < p2 [i+s].x) continue;
		i+=s;
	}
	if (i == 0) return false;
	if (p2 [i] == punct) return true;
	return false;
}

long long semn (ii punct, int ind)
{
	ii p1, p2;
	if (p [ind].y > p [ind+1].y)
	{
		p1=p [ind+1];
		p2=p [ind];
	}
	else
	{
		p1=p [ind];
		p2=p [ind+1];
	}
	long long a=p1.y-p2.y, b=p2.x-p1.x, c=(long long)p1.x*p2.y - (long long)p1.y*p2.x;
	return a*punct.x+b*punct.y+c;
}

int cb1 (int yy)
{
	int s=1<<10, i;
	for (i=0; s; s >>= 1)
		if (nintr >= i+s && intr [i+s].y1 <= yy)
			i+=s;
	return i;
}

int cb2 (ii punct, int k)
{
//	fprintf (stderr, "(%d %d) %d %d %d %d", punct.x, punct.y, segm [k] [1].second, segm [k] [nrsegm [k]].second, semn (punct, segm [k] [1].second), semn (punct, segm [k] [nrsegm [k]].second));
	if (semn (punct, segm [k] [1].second) > 0) return 0;
	if (semn (punct, segm [k] [nrsegm [k]].second) < 0) return 0;

//	fprintf (stderr, "exist!\n");

	int s=1<<10, i;
	for (i=0; s; s >>= 1)
	{
		if (nrsegm [k] < i+s) continue;
		if (semn (punct, segm [k] [i+s].second) <= 0)
			i+=s;
	}
	if (semn (punct, segm [k] [i+s].second) == 0) return 1;
/*	int j;
	for (j=1; j <= nrsegm [k]; ++j)
		fprintf (stderr, "%d\n", segm [k] [j].second);
	fprintf (stderr, "nrsegm [k]=%d\n", nrsegm [k]);*/
	return i;
}

bool interior (ii punct)
{
	if (punct.y < intr [1].y1 || punct.y > intr [nintr].y2) return false;
	if (exista (punct)) 
		return true;
//	fprintf (stderr, "!%d %d\n", punct.y, intr [1].y1);
	int k=cb1 (punct.y);
//	fprintf (stderr, "k=%d\n", k);
	if (cb2 (punct, k) % 2 == 1)
		return true;
	if (punct.y == intr [k].y1 && k != 1)
		if (cb2 (punct, k-1) % 2 == 1)
			return true;
	return false;
}

int rez ()
{
	int i, num=0;
	ii punct;
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d", &punct.x, &punct.y);
		if (interior (punct))
			++num;
	}
	return num;
}

int main ()
{
	freopen ("poligon.in", "r", stdin);
	freopen ("poligon.out", "w", stdout);
	scan ();
	bucatele ();
	printf ("%d\n", rez ());
	return 0;
}