Cod sursa(job #429532)

Utilizator laserbeamBalan Catalin laserbeam Data 30 martie 2010 11:25:34
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
// Catalin Balan
// Tue Mar 30 09:18:56 EEST 2010
// preONI 2005 - Poligon

#include <cstdio>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

#define NMAX 816

#define FIN "poligon.in"
#define FOUT "poligon.out"

// PARSARE
#define CHUNK 8192
char g_buf[CHUNK];
int g_p=CHUNK-1;

inline int get()
{

	int x = 0;
	while (g_buf[g_p] < '0' || g_buf[g_p] > '9')
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;

	while (g_buf[g_p] >= '0' && g_buf[g_p] <= '9')
	{
		x = x*10 + g_buf[g_p]-'0';
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
	}
	return x;
}
// END PARSARE

typedef pair<int, int> pct; 
typedef long long i64;
vector<int> benzi[NMAX]; // benzi[i] contine segmentele ce fac parte din banda i
int vert[NMAX]; // abscisele la care se delimiteaza benzile
pct puncte[NMAX]; // tin minte punctele (X,Y)
pct segm[NMAX]; // tin minte segmentele sub forma de indici de puncte (pct din dr, pct din st)
int ord[NMAX]; // indicii punctelor sortati dupa X
int n,m,k; // k - nr de benzi

bool cmp2( int a, int b )
{
	return (puncte[a] < puncte[b]);
}
bool cmp( pct a, pct b )
{
	if ( puncte[a.first] == puncte[b.first])
		return cmp2(a.second, b.second);
	return cmp2(a.first, b.first);
}

// vezi daca un punct e deasupra unui segment cu pct a in st si pct b in dr
int deasupra( int x, int y, int xa, int ya, int xb, int yb )
{
	if ( y >= ya && y >= yb) return true;
	if ( y <= ya && y <= yb) return false;

	xb -= xa;
	yb -= ya;
	x  -= xa;
	y  -= ya;

	if ( ( (i64)y*(i64)xb - (i64)x*(i64)yb ) >= 0 ) return true;
	return false;

}

int numaraSegm( int x, int y, int banda )
{
	vector<int>::iterator it;
	int numar = 0;
	for (it = benzi[banda].begin(); it != benzi[banda].end(); ++it)
	{
		numar += deasupra( x, y, puncte[segm[*it].first].first,
								 puncte[segm[*it].first].second,
								 puncte[segm[*it].second].first,
								 puncte[segm[*it].second].second );
	}
	return numar;
}

int inPoligon( int x, int y )
{
	// cauta banda in care e punctul
	int st = 0, dr = k;
	int ind = 0;
	while (st <= dr)
	{
		int mij = (st+dr)>>1;
		if ( x >= vert[mij])
		{
			ind = mij;
			st = mij+1;
		} else
			dr = mij-1;
	}
	return (numaraSegm( x, y, ind ) & 1);
}

int main(int argv, char ** argc)
{
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	n = get();
	m = get();
	int x = get();
	int y = get();
	puncte[1] = make_pair(x,y);
	for (int i = 2; i <= n; ++i)
	{
		int x,y;
		x = get();
		y = get();
		puncte[i] = make_pair(x,y);
		if (puncte[i] < puncte[i-1])
			segm[i-1] = make_pair(i,i-1);
		else segm[i-1] = make_pair(i-1,i);

		ord[i] = i;
	}
	ord[1] = 1;
	if (puncte[1] < puncte[n])
		segm[n] = make_pair(1,n);
	else segm[n] = make_pair(n,1);

	sort(segm+1, segm+n+1, cmp);
	sort(ord+1, ord+n+1, cmp2);



	// delimiteaza benzile
	vert[0] = -1;
	k = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (puncte[ord[i]].first > vert[k])	vert[++k] = puncte[ord[i]].first;
	}

	vert[++k] = 100000;

	// pune segmentele in benzi
	int aux[NMAX], sz = 0;
	int j = 1;  
	for (int i = 0; i < k; ++i)
	{
		// scoate elemente
		for (int l = 1; l <= sz; ++l)
			if ( puncte[ segm[ aux[l] ].second ].first <= vert[i])
			{
				aux[l] = aux[sz];
				--sz;--l;
			}
		// adauga elemente
		while ( j <= n && vert[i+1] > puncte[segm[j].first].first)
		{
			if (puncte[segm[j].first].first == puncte[segm[j].second].first) continue;
			aux[++sz] = j;
			++j;
		}
		benzi[i].assign(aux+1, aux+sz+1);
	}
	

	int rez = 0;
	for (;m;--m)
	{
		x = get();
		y = get();
		rez += inPoligon(x,y);
	}

	printf("%d\n", rez);

	return EXIT_SUCCESS;
}