Cod sursa(job #455191)

Utilizator prisonbreakMichael Scofield prisonbreak Data 13 mai 2010 10:11:35
Problema Poligon Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.39 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.000000000001;
//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);
}
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 && X [mij + 1] >= x) return mij;
		if (X [mij] >= x)
			//soll = mij;
			dr = mij - 1;
		else st = mij + 1;
	}
	return dr;
}
inline bool equal (db a, db b) {
	a-=b;
	if (a < 0) a = -a;
	if (a < eps) return 1;
	return 0;

}
inline db funct (db x1, db y1, db x2, db y2, db x3, db y3)
{	
	db A = db (x3 - x1) * db (y2 - y1) - db (x2 - x1) * db (y3 - y1);
	//printf ("A:%f\n", A);
	if (equal (A, (db)0)) {
		return 2; OK = 1;
	}
	if (A > 0) return 1;
	return 0;

}
inline bool bin2_search (int band, int x, int y)
{	
	int st, dr, mid, soll = -1; int ok; OK = 0;
	int a = 0; //signed mid;
	//printf ("BAU\n");
	for (st = 1, dr = LG [band], mid = (st + dr >> 1); st <= dr; mid = st + dr >> 1) {
		ok = funct (x, (db)y, X [band], PP [band][mid].y1, X [band + 1], PP [band][mid].y2);
		if (ok == 2) return 1;
		if (ok) { 
			soll = mid;//printf ("%d\n", ok);
			dr = mid - 1;
		}
		else st = mid + 1;
		//printf ("%d\n", ok);
	} //printf ("%d %d %d\n", soll, LG [band], LG [band] - soll + 1); 
	if (soll == -1) return 0;
	soll = LG [band] - soll + 1;
	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");
	}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 (a == X [1]) band = 1;
		//printf ("%d\n", band); 
		//printf ("%d ", i); //printf ("%d\n", PP [band].size () - i);
		if (bin2_search (band, a, b)) ++nr;
		else
		if (band + 1 < NRB && a == X [band + 1] && bin2_search (band + 1, a, b)) 
			 ++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;
}