Cod sursa(job #552305)

Utilizator ilincaSorescu Ilinca ilinca Data 12 martie 2011 02:39:24
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 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];
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);
}

double xmijloc (int p1, int p2)
{
	double mx;
	mx=((double)p [p1].x + p [p2].x)/2;
	return mx;
}

void bucatele ()
{
	int i, j;
	sort (p+1, p+1+n);
	for (i=1; i < n; ++i)
	{
		j=i+1;
		while (j < n && p [j+1].y == p [j].y)
			++j;
		intr [++nintr]=ii (p [i].y, p [j].y);
		i=j;
	}
	for (i=1; i <= nintr; ++i)
	{
		for (j=1; j < n; ++j)
		{
			if (p [j].y < intr [i].y1 || p [j].y > intr [i].y2) continue;
			if (p [j+1].y < intr [i].y1 || p [j+1].y > intr [i].y2) continue;
			segm [i] [++nrsegm [i]]= (mp (xmijloc (j, j+1), j));
		}
		sort (segm [i]+1, segm [i]+1+nrsegm [1]);
	}
}

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

int semn (ii punct, int ind)
{
	return (p [ind].x-punct.x)*(p [ind+1].y-punct.y)-(p [ind+1].x-punct.x)*(p [ind].y-punct.y);
}

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)
{
	if (semn (punct, segm [k] [1].second) < 0) return 0;
	if (semn (punct, segm [k] [nrsegm [k]].second) > 0) return 0;
	
	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 (exista (punct)) 
		return true;
	if (punct.y < intr [1].y1 || punct.y > intr [nintr].y2) return false;
	int k=cb1 (punct.y);
	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;
}