Cod sursa(job #455026)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 12 mai 2010 22:38:34
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.52 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define nmax 810
#define XMAX 60005
#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 ffpoint {float y1, y2;};
struct fpoint {float x, y;};
vector <pair <point, point> > seg;
ffpoint PP [nmax][nmax];
int LG [nmax];
point ins [nmax], P1 , P2 ;
int n, m, X [nmax]; bool viz [XMAX]; int NRB;
const double eps = 0.00000000001;
//Beg - cbin1, D - cbin2;
inline bool cmp (const ffpoint &a, const ffpoint &b) {
	return a.y1 == b.y1 ? (a.y2 < b.y2) : (a.y1 < b.y1);
}
inline double det (double x1, double x2, double y1, double y2, double x) {
	return ((y2 - y1)/(x2-x1) * (x - x1)) + y1;
}
double ceas_trig (fpoint p0, fpoint p1, fpoint p2) {
	return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}
void preproc ()
{	
	int i;
	double y1, y2;
	int bx1, bx2, j;
	ffpoint ff;
	// |
	//BEG.pb (mp (0, seg [0].f.x));
	for (j = 2; j <= X [0]; j++)
	{
		// |extract* * * * coordx|
		bx1 = X [j - 1];
		bx2 = X [j];
		++NRB;
		//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 <= bx1 && seg [i].s.x >= bx2) { // | - 
				db tg = (db) (seg [i].s.y - seg [i].f.y) / (db) (seg [i].s.x - seg [i].f.x);
				y1 = (tg * (db)(bx1 - seg [i].f.x)) + seg [i].f.y;
				y2 = (tg * (db)(bx2 - seg [i].f.x)) + seg [i].f.y;
				ff.y1 = y1; ff.y2 = y2;
				PP [NRB][++LG [NRB]] = ff;
			}
		sort (PP [NRB] + 1, PP [NRB] + LG [NRB] + 1, cmp);
			//BEG.pb (mp (bx1, bx2)); // aici cauti binar 1
	}
} int OK;
inline int bin1_search (int x)
{	
	int st, dr, mij;
	for (st = 1, dr = X [0], mij = st + dr >> 1; st <= dr; mij = st + dr >> 1) {;
		if (X [mij] >= x)
			//soll = mij;
			dr = mij - 1;
		else if (X [mij] < x) st = mij + 1;
	}
	return dr;
}
inline bool equal (db a, db b) {
	if (a < 0) a -= a;
	if (a < eps) return 1;
	return 0;

}
inline db funct (fpoint P1, fpoint P2, db x1, db y1)
{	
	fpoint P3;
	P3.x = x1; P3.y = y1;
	db c = ceas_trig (P1, P2, P3);
	if (equal (c, (db)0)) {
		OK = 1;
		return 2;
	}
	if (c > 0) return 1;
	return 0;

}
inline bool bin2_search (int band, int x, int y)
{	
	int st, dr, mid, soll = -1; fpoint P1, P2;
	int a = 0; //signed mid;
	for (st = 1, dr = LG [band], mid = st + dr >> 1; st <= dr; mid = st + dr >> 1) {
		P1.x = X [band]; P2.x = X [band + 1];
		P1.y = PP [band][mid].y1; P2.y = PP [band][mid].y2;
		a = funct (P1, P2, x, y);
		//mid + 1 < PP [band].size () ? b = funct (PP [band][mid + 1].s.f, PP [band][mid + 1].s.s, x, y) : b = -inf;
		if (a == 2) return 1;
		else if (a > 0) st = mid + 1;
		else {
			dr = mid - 1;
			soll = mid;
		}
		//printf ("%d %d\n", st, dr);
	}
	if (soll == -1) return 0;
	soll = LG [band] - soll + 1;
	//printf ("%d\n", soll);
	if (soll & 1) return 1;
	return 0;
	//f (funct (PP [band][PP[band].size ()-1].s.f, PP [band][PP[band].size()-1].s.f, x, y) < 0) return 0;
	//
//	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);
	X [++X [0]] = ins [1].x;viz [X [X [0]]] = 1;
	//seg.pb (mp (P1, P2)); //seg.pb (mp (P1, P2));
	for (i = 2; i <= n + 1; i++) {
		if (i != n + 1)
			scanf ("%d%d\n", &ins [i].x, &ins [i].y);
		else ins [i].x = ins [1].x, ins [i].y = ins [1].y;
		P1 = ins [i - 1];
		P2 = ins [i];
		if (P1.x > P2.x || (P1.x == P2.x && P1.y > P2.y))
		{
			swap (P1.x, P2.x);
			swap (P1.y, P2.y);
		}
		seg.pb (mp (P1, P2));
		if (!viz [ins [i].x]) {
			X [++X [0]] = ins [i].x;
			viz [ins [i].x] = 1;
		}
	}
	sort (X + 1, X + X [0] + 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);
	preproc ();
	/*printf ("********************************************************\n");
	for (band = 1; band <= NRB; band++) {
		printf ("%d-> %d %d\n", band, X [band], X [band + 1]);
		for (i = 1; i <= LG [band]; i++)
			printf ("%f %f\n", PPI.y1, PPI.y2);
		printf ("\n");
	}*/
	nr = 0;
	while (m--) {
		scanf ("%d%d\n", &a, &b);
		if (a < X [1] || a > X [X [0]]) continue;
		band = bin1_search (a);
		if (band == X [1]) band = 1;
		//printf ("%d\n", band); 
		if (band != -1) {
			i = bin2_search (band, a, b);
		//	printf ("%d ", i); //printf ("%d\n", PP [band].size () - i);
			if (i) ++nr;
		}
		//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;
}