Cod sursa(job #781651)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 24 august 2012 19:49:18
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAXN 802
#define EPS 1e-8
#define MAXM 60010
#define point pair<double, double>
#define INFINITY make_pair(-1.0, -1.0)
#define x first
#define y second

point A[MAXN];
point B[MAXM];
int r, t;
double V[MAXN];
point V1[MAXN], V2[MAXN];
int Ind[MAXN];
int i, j, nr, poz;
int N, M;
point X, Y, Z, T;
double semn;
int st, dr, mij, sol;
int Ans;

inline double det(const point &A, const point &B, const point &C)
{
	return (A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x);
}

inline int cmp_real(const double &a, const double &b)
{
	if (a+EPS < b) return -1;
	if (b+EPS < a) return 1;
	return 0;
}

inline point intersect(const point &A, const point &B, const point &C, const point &D)
{
	double x1, x2, x3, x4, y1, y2, y3, y4, q, w, e;
	x1 = A.x; x2 = B.x; x3 = C.x; x4 = D.x;
	y1 = A.y; y2 = B.y; y3 = C.y; y4 = D.y;
	
	e = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
	q = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - x4 * y3);
	w = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - x4 * y3);
	q = q / e;
	w = w / e;
	return make_pair(q, w);
}

inline bool OnSegment(point A, point B, point C)
{
	if (cmp_real(A.x, B.x) == 1)
		swap(A, B);
	if (cmp_real(C.x, A.x) == -1) return false;
	if (cmp_real(B.x, C.x) == -1) return false;
	return true;
}

inline bool cmp(const point &q, const point &w)
{
	return (cmp_real(q.y, w.y) < 0);
}

inline point rotation(const point &A, const double angle)
{
	double X, Y;
	X = A.x * cos(angle) - A.y * sin(angle);
	Y = A.x * sin(angle) + A.y * cos(angle);
	return make_pair(X, Y);
}

int main()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	
	scanf("%d %d",&N, &M);
	for (i = 1; i <= N; ++i){
		scanf("%d %d",&r, &t);
		A[i].x = r;
		A[i].y = t;
		A[i] = rotation(A[i], 0.002);
		V[i] = A[i].x;
	}
	A[N+1] = A[1];
	
	for (i = 1; i <= M; ++i){
		scanf("%d %d",&r, &t);
		B[i].x = r;
		B[i].y = t;
		B[i] = rotation(B[i], 0.002);
	}
	
	sort(B+1, B+M+1);
	sort(V+1, V+N+1);
	
	poz = 1;
	
	for (i = 1; i < N; ++i){
		if (cmp_real(V[i], V[i+1]) == 0) continue;
		
		X = make_pair(V[i], -1.0);
		Y = make_pair(V[i+1], -1.0);
		Z = make_pair(V[i+1], 60001.0);
		T = make_pair(V[i], 60001.0);
		
		nr = 0;
		for (j = 1; j <= N; ++j){
			V1[++nr] = intersect(X, T, A[j], A[j+1]);
			V2[nr] = intersect(Y, Z, A[j], A[j+1]);
			if (OnSegment(A[j], A[j+1], V1[nr]) == false){
				--nr;
				continue;
			}
			if (OnSegment(A[j], A[j+1], V2[nr]) == false){
				--nr;
				continue;
			}
		}
		for (j = 1; j <= nr; ++j)
			Ind[j] = j;
		sort(V1+1, V1+nr+1, cmp);
		sort(V2+1, V2+nr+1, cmp);
		
		while (poz <= M && cmp_real(B[poz].x, V[i+1]) < 0){
			
			sol = 0;
			st = 1 << 9;
			for (sol = 0; st; st >>=1)
				if (sol + st <= nr && cmp_real(det(V1[sol+st], V2[sol+st], B[poz]), 0.0) >= 0)
					sol |= st;
		
			if (sol == 0){
				++poz;
				continue;
			}
			
			semn = det(V1[sol], V2[sol], B[poz]);
			if (cmp_real(semn, 0.0) == 0){
				++Ans;
				++poz;
				continue;
			}
			
			if (sol % 2 == 1)
				++Ans;
			++poz;
		}
	}
	
	printf("%d\n", Ans);
	return 0;
}