Cod sursa(job #552637)

Utilizator ilincaSorescu Ilinca ilinca Data 12 martie 2011 17:31:00
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define nmax 805
#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)
{
	double mx;
	mx=(double)(p [p1].x + p [p2].x)/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), 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 (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-1;
}

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;
	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);
	if (punct.y < intr [1].y1 || punct.y > intr [nintr].y2) return false;
	int k=cb1 (punct.y);
	//fprintf (stderr, "%d\n", k);
	if (cb2 (punct, k) % 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;
}