Cod sursa(job #429644)

Utilizator laserbeamBalan Catalin laserbeam Data 30 martie 2010 12:43:06
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.93 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;
int benzi[NMAX][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
int segmVert[NMAX];
double auxComp[NMAX];

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);
}

bool cmp3( int a, int b )
{
	return puncte[segm[a].first].first < puncte[segm[b].first].first;
}

bool cmp4( int a, int b )
{
	return (auxComp[a] < auxComp[b]);
}

// 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;
	i64 s = (i64)y*(i64)xb - (i64)x*(i64)yb;
	if ( s > 0 ) return 1;
	if ( s == 0) return 10000;
	return 0;
}

int numaraSegm( int x, int y, int banda )
{
	vector<int>::iterator it;
	int rez = 0;
	int st = 1, dr = benzi[banda][0];
	while ( st <= dr )
	{
		int mij = (st+dr)>>1;
		int q = deasupra( x, y, puncte[ segm[ benzi[banda][mij] ].first ].first, 
								puncte[ segm[ benzi[banda][mij] ].first ].second, 
								puncte[ segm[ benzi[banda][mij] ].second ].first, 
								puncte[ segm[ benzi[banda][mij] ].second ].second );
		if ( q == 10000 ) return 1;
		if ( q )
		{
			rez = mij;
			st = mij+1;
		} else
			dr = mij-1;
	}
	return rez;

}

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);
}

double mijSegm( double xLine, int id )
{
	double x1 = puncte[ segm[id].first ].first;
	double y1 = puncte[ segm[id].first ].second;
	double x2 = puncte[ segm[id].second ].first;
	double y2 = puncte[ segm[id].second ].second;

	x1-=x2;
	y1-=y2;
	xLine-=x2;
	double yLine = (y1*xLine)/x1;
	yLine+=y2;
	return yLine;
}

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, nrv = 0;
	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)
			{
				segmVert[++nrv] = j;
				continue;
			}
			aux[++sz] = j;
			++j;
		}
		double midLine = (vert[i]+vert[i+1])>>1;
		for ( int l = 1; l <= sz; ++l )
			auxComp[aux[l]] = mijSegm( midLine, aux[l] );
		sort(aux+1, aux+sz+1, cmp4);
		for ( int l = 1; l <= sz; ++l)
			benzi[i][l] = aux[l];
		benzi[i][0] = sz;
	}
	
	sort(segmVert+1, segmVert+n+1, cmp3);

	int rez = 0;
	for (;m;--m)
	{
		x = get();
		y = get();

		int st = 1, dr = nrv;
		int answ = 0;
		while (st <= dr)
		{
			int mij = (st+dr)>>1;
			if (puncte[ segm[ segmVert[mij] ].first ].first >= x)
			{
				answ = mij;
				st = mij+1;
			} else
				dr = mij-1;
		}
		if ( answ && x == puncte[ segm[ segmVert[answ] ].first ].first)
		{
			if ( y <= puncte[ segm[ segmVert[answ] ].second ].second && 
				 y >= puncte[ segm[ segmVert[answ] ].first ].second ) 
			{
				++rez;
				continue;
			}
		}


		rez += inPoligon(x,y);
	}

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

	return EXIT_SUCCESS;
}