Cod sursa(job #781664)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 24 august 2012 20:11:19
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.82 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 &C, const point &D)
{
	return make_pair(A.x, D.y + (D.y - C.y) * (A.x - D.x) / (D.x - C.x));
}

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){
			if (A[j].x <= V[i] && A[j+1].x <= V[i]) continue;
			if (A[j].x >= V[i+1] && A[j+1].x >= V[i+1]) continue;
			V1[++nr] = intersect(X, A[j], A[j+1]);
			V2[nr] = intersect(Y, A[j], A[j+1]);
		}

		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 && det(V1[sol+st], V2[sol+st], B[poz]) >= -EPS)
					sol |= st;
		
			if (sol == 0){
				++poz;
				continue;
			}
			
			if (sol & 1){
				++Ans;
				++poz;
				continue;
			}
			
			semn = det(V1[sol], V2[sol], B[poz]);
			if (cmp_real(semn, 0.0) == 0){
				++Ans;
				++poz;
				continue;
			}
		
			++poz;
		}
	}
	
	printf("%d\n", Ans);
	return 0;
}