Cod sursa(job #451739)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 9 mai 2010 21:48:17
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.64 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
#define PPI PP[band][i]
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.y == b.f.y ? (a.f.x > b.f.x) : (a.f.y > b.f.y);
}
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, y1, y2;
	point bx1, bx2;
	fpoint ff;
	// |
	BEG.pb (mp (0, seg [0].f.x));
	for (nrbenzi = 2; nrbenzi <= n; nrbenzi++)
	{
		bx1 = ins [nrbenzi - 1];
		bx2 = ins [nrbenzi];
		while (nrbenzi <= n && ins [nrbenzi].x == ins [nrbenzi + 1].x) ++nrbenzi;
		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;
                                                y1 = det (seg [i].f.x, seg [i].s.x, seg [i].f.y, seg [i].s.y, bx1.x);
						mijy = (y1 + seg [i].s.y) / (db)2;
						ff.x = mijx; ff.y = mijy;
						PP [BEG.size ()].pb (mp (ff, mp (seg [i].f, seg [i].s)));
					} 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) {
					y2 = det (seg [i].f.x, seg [i].s.x, seg [i].f.y, seg [i].s.y, bx2.x);
					if (seg [i].f.x < bx1.x) {
						y1 = det (seg [i].f.x, seg [i].s.x, seg [i].f.y, seg [i].s.y, bx1.x);
						mijy = (y1 + y2) / (db) 2;
						mijx = (bx1.x + bx2.x) / (db) 2;
					}
					else  {
						mijx = (seg [i].f.x + bx1.x ) / (db) 2;
						mijy = (seg [i].f.y + y2) /(db)2;
					}
					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));
	}
}
inline int bin1_search (int x, int y)
{	
	int st, dr, mij;
	for (st = 0, 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 -1;
}
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;;
	for (st = 0, dr = PP [band].size () - 1, 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 > 0)
			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 && b < 0)  return mid;
		else if (a < 0 && c > 0) return mid + 1;
		else if (a > 0) dr = mid - 1;
		else if (a < 0) st = mid + 1;
		else if (a == 0) return mid;
	}//return 200;
	int ok = funct (PP [band][PP[band].size ()-1].s.f, PP [band][PP[band].size()-1].s.f, x, y);
	if (ok < 0) return 0;
	else if (ok == 0) return 1;
	return PP [band].size ();
}
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);
	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]));
	sort (ins + 1, ins + n + 1, cmp);
	preproc ();
	for (i = 0; i < BEG.size (); i++) 
		sort (PP [i].begin (), PP [i].end (), comp);	
	nr = 0;
	while (m--) {
		scanf ("%d%d\n", &a, &b);
		band = bin1_search (a, b);
		if (band > 0) {
			i = bin2_search (band, a, b);
			if (i & 1) ++nr;
		}
	}
	printf ("%d\n", nr);
	return 0;
}