Cod sursa(job #451091)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 8 mai 2010 23:44:56
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.58 kb
#include <cstdio>
#include <algorithm>
#include <vector>



#define nmax 810
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define db double
using namespace std;

struct point {int x, y;};
struct fpoint {float x, y;};
vector <pair <point, point> > seg;
vector <pair <int, int> > BEG;
vector <pair <double, double> > D [nmax];
vector <pair <fpoint, pair <point, point> > > PP [nmax];
point ins [nmax], P1 , P2 ;
int n, m, nrbenzi;
//Beg - cbin1, D - cbin2;
inline bool cmp (const point &a, const point &b) {
	return a.x == b.x ? (a.y < b.y) : (a.x < b.x);
}
inline bool comp (const pair <fpoint ,pair <point, point> > &a, const pair <fpoint, pair <point, point> > &b) {
	return a.f.x == b.f.x ? (a.f.y < b.f.y) : (a.f.x < b.f.x);
}
inline double det (double x1, double x2, double y1, double y2, double x) {
	return ((y2 - y1)/(x2-x1) * (x - x1)) + y1;
}
double ceas_trig (point p0, point p1, point p2) {
	return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}
void preproc ()
{	
	int i;
	double mijy, mijx;
	point bx1, bx2;
	fpoint ff;
	// |
	BEG.pb (mp (0, seg [0].f.x));
	for (nrbenzi = 2; nrbenzi <= n; nrbenzi++)
	{
		// |extract* * * * coordx|
		bx1 = ins [nrbenzi - 1];
		bx2 = ins [nrbenzi];
		while (nrbenzi <= n && ins [nrbenzi].x == ins [nrbenzi + 1].x) ++nrbenzi;
		//printf ("BX %d %d %d %d BX\n", bx1.x, bx1.y, bx2.x, bx2.y);
		for (i = 0; i < n; i++) {
			if (seg [i].f.x >= bx2.x || seg [i].s.x <= bx1.x) continue;// | | 
			if (seg [i].f.x <= bx2.x && seg [i].s.x >= bx1.x) { // | - |				
				if (seg [i].s.x <= bx2.x) { // | -|
					if (seg [i].f.x < bx1.x) {//-|- |
						mijx = (seg [i].s.x + bx1.x) / 2;
                                                mijy = det (seg [i].f.x, seg [i].s.x, seg [i].f.y, seg [i].s.y, bx1.x);
						mijy /= 2;
						ff.x = mijx; ff.y = mijy;
						PP [BEG.size ()].pb (mp (ff, mp (seg [i].f, seg [i].s)));
					
						//printf ("****%d %d***\n", seg [i].f.x, bx1.x);
					} else { // |-|
						mijx = (seg [i].s.x + seg [i].f.x) / (db)2;
						mijy = (seg [i].s.y + seg [i].f.y) / (db)2;
						ff.x = mijx; ff.y = mijy;
						PP [BEG.size ()].pb (mp (ff, mp (seg [i].f, seg [i].s)));
					}
				}
				else if (seg [i].s.x > bx2.x) {
					mijy = det (seg [i].f.x, seg [i].s.x, seg [i].f.y, seg [i].s.y, bx1.x);
					mijx = (bx2.x + seg [i].f.x) / (db)2;
					mijy /= (db)2;//printf ("?!?@?@#?\n");
					ff.x = mijx; ff.y = mijy;
					PP [BEG.size ()].pb (mp (ff, mp (seg [i].f, seg [i].s)));
				}
			}
		}
		BEG.pb (mp (bx1.x, bx2.x)); // aici cauti binar 1
	}
}
inline int bin1_search (int x, int y)
{	
	int st, dr, mij;
	for (st = 1, dr = BEG.size (), mij = st + dr >> 1; st <= dr; mij = st + dr >> 1) {
		if (BEG [mij].f <= x && BEG [mij].s >= x) return mij;
		else if (BEG [mij].f > x) dr = mij - 1;
		else if (BEG [mij].s < x) st = mij + 1;
	}
	return 0;
}
inline int funct (point P1, point P2, int x1, int y1)
{	
	point P3;
	P3.x = x1; P3.y = y1;
	return ceas_trig (P1, P2, P3);
}
#define inf 1000000
inline int bin2_search (int band, int x, int y)
{	
	int st, dr, mid, a = 0, b, c, soll = 0;
	for (st = 0, dr = PP [band].size (), mid = st + (dr - st) / 2; st <= dr; mid = st + (dr - st) / 2) {
		a = funct (PP [band][mid].s.f, PP [band][mid].s.s, x, y);
		c = inf; b = -inf;
		if (mid - 1 > -1)
			b = funct (PP [band][mid - 1].s.f, PP [band][mid - 1].s.s, x, y);
		if (mid + 1 <= PP [band].size ())
			c = funct (PP [band][mid + 1].s.f, PP [band][mid + 1].s.s, x, y);
		if (a > 0 && c < 0 || a < 0 && b > 0) return mid;
		else if (a > 0) st = mid + 1;
		else if (a < 0) dr = mid - 1;
		else if (a == 0) return mid;
		soll = mid;
		//printf ("%d %d\n", st, dr);
	}
	return soll;
}
int main () {
	int i, a, b, band, nr = 0;
	freopen ("poligon.in", "r", stdin);
	freopen ("poligon.out", "w", stdout);
	
	scanf ("%d%d\n", &n, &m);
	scanf ("%d%d\n", &ins [1].x, &ins [1].y);
	
	//seg.pb (mp (P1, P2)); //seg.pb (mp (P1, P2));
	for (i = 2; i <= n; i++) {
		scanf ("%d%d\n", &ins [i].x, &ins [i].y);
		P1.x = ins [i - 1].x;
		P1.y = ins [i - 1].y;
		P2.x = ins [i].x;
		P2.y = ins [i].y;
		if (P1.x > P2.x) seg.pb (mp (P2, P1));
		else seg.pb (mp (P1, P2));
	}if (ins [n].x > ins [1].x) seg.pb (mp (ins [1], ins [n]));
	else seg.pb (mp (ins [n], ins [1]));
	//for (i = 0; i < n; i++) 
	//	printf ("%d %d %d %d\n", seg [i].f.x, seg [i].f.y, seg [i].s.x, seg [i].s.y);
	//sort (seg.begin (), seg.end (), cmp);
	sort (ins + 1, ins + n + 1, cmp);
	//for (i = 1; i <= n; i++) 
	//	printf ("%d %d\n", ins [i].x, ins [i].y);
	//printf ("---------------------------------------\n");
	preproc ();
	//printf ("********************************************************\n");
	//for (i = 0; i < BEG.size (); i++) printf ("%d %d\n", BEG [i].f, BEG [i].s);
	for (i = 0; i < BEG.size (); i++) 
		sort (PP [i].begin (), PP [i].end (), comp);	
	/*printf ("********************************************************\n");
	for (band = 0; band < BEG.size (); band++) {
		printf ("%d\n", band);
		for (i = 0; i < PP [band].size (); i++)
			printf ("%d %d %d %d\n", PP [band][i].s.f.x, PP [band][i].s.f.y, PP [band][i].s.s.x, PP [band][i].s.s.y);
		printf ("\n");*/
	nr = 0;
	while (m--) {
		scanf ("%d%d\n", &a, &b);
		band = bin1_search (a, b);
		//printf ("%d\n", band);
		//for (i = 0; i < PP [band].size (); i++)
		//	printf ("%d %d %d %d\n", PP [band][i].s.f.x, PP [band][i].s.f.y, PP [band][i].s.s.x, PP [band][i].s.s.y);
		//i = bin2_search (band, a, b);
		//printf ("%d ", i); printf ("%d\n", PP [band].size () - i);
		if ((PP [band].size () - i) & 1) ++nr;
		//else printf ("NU ESTE\n");
		//printf ("%d\n", band);*/
	}
	printf ("%d\n", nr);
	//for (i = 1; i <= nrbenzi; i++) printf ("%d %d\n", V [i].x, V [i].y);
	return 0;
}