Cod sursa(job #574285)

Utilizator mayhemx77Voinea C. Vladimir mayhemx77 Data 6 aprilie 2011 23:48:16
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.01 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>
#define maxn 20
#define maxm 27
#define inf 0x3f3f3f3f
#define mp make_pair

using namespace std;

struct punct {
	int x, y;
};

struct segm {
	punct a, b;
};

int n, m;
int i, j;
punct robot[maxn], p1, p2;
int nr[maxm], nr_nou[maxm];
punct polig[maxm][256], polig_nou[maxm][256];
punct ref, start, stop; 
vector <pair<int, int> > g[maxm][256];
vector <double> cst[maxm][256];
int i1, i2, jj1, jj2;
double cmin[maxm][256];
int usd[maxm][256];

bool cmp(segm a, segm b) {
	if (atan2(a.b.y - a.a.y, a.b.x - a.a.x) < atan2(b.b.y - b.a.y, b.b.x - b.a.x))
		return true;
	return false;
}

inline void det_dr_sus(punct polig[], int n, punct &dr_sus) {
	int i;
	dr_sus = polig[1];
	for (i = 2; i <= n; i++) 
		if (polig[i].y > dr_sus.y || (polig[i].y == dr_sus.y && polig[i].x > dr_sus.x))
			dr_sus = polig[i];
}

inline void det_st_jos(punct polig[], int n, punct &st_jos) {
	int i;
	st_jos = polig[1];
	for (i = 2; i <= n; i++) 
		if (polig[i].y < st_jos.y || (polig[i].y == st_jos.y && polig[i].x < st_jos.x))
			st_jos = polig[i];
}

void make_new_polig(int ind) {
	int i, nrt, tx, ty;
	punct ant, dr_sus, st_jos, ref_copy;
	segm t[256];

	nrt = 0;
	for (i = n + 1; i > 1; i--) {
		nrt++;
		t[nrt].a = robot[i]; t[nrt].b = robot[i - 1];
	}

	for (i = 1; i <= nr[ind]; i++) {
		nrt++;
		t[nrt].a = polig[ind][i]; t[nrt].b = polig[ind][i + 1];
	}


	sort(t + 1, t + nrt + 1, cmp);	

	ant.x = ant.y = 0;
	nr_nou[ind] = nrt;

	for (i = 1; i <= nrt; i++) {
		polig_nou[ind][i].x = ant.x + (t[i].b.x - t[i].a.x);
		polig_nou[ind][i].y = ant.y + (t[i].b.y - t[i].a.y);
		ant = polig_nou[ind][i];
	}

	det_dr_sus(robot, n, dr_sus);
	det_st_jos(polig[ind], nr[ind], st_jos);
		
	tx = st_jos.x - dr_sus.x; 
	ty = st_jos.y - dr_sus.y;

	ref_copy.x = ref.x + tx;
	ref_copy.y = ref.y + ty;

	det_st_jos(polig_nou[ind], nr_nou[ind], st_jos);

	tx = ref_copy.x - st_jos.x;
	ty = ref_copy.y - st_jos.y;

	for (i = 1; i <= nr_nou[ind]; i++) {
		polig_nou[ind][i].x += tx;
		polig_nou[ind][i].y += ty;
	}

	polig_nou[ind][nr_nou[ind] + 1] = polig_nou[ind][1];

}

inline int det(punct a, punct b, punct c) {
	return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y);
}

inline bool on_segment(punct p, punct p1, punct p2) {
	int xmin, xmax, ymin, ymax;
	xmin = min(p1.x, p2.x); xmax = max(p1.x, p2.x);
	ymin = min(p1.y, p2.y); ymax = max(p1.y, p2.y);
	if (det(p, p1, p2) == 0 && p.x >= xmin && p.x <= xmax && p.y >= ymin && p.y <= ymax)
		return 1;
	return 0;
}

inline int polig_area(punct polig[], int n) {
	int area = 0, i;
	for (i = 1; i <= n; i++)
		area = area + (polig[i].x * polig[i + 1].y - polig[i].y * polig[i + 1].x);
	return abs(area);
}

inline bool point_in_poly(punct p, punct polig[], int n) {
	int i, area, tr_area;
	for (i = 1; i <= n; i++)
		if (on_segment(p, polig[i], polig[i + 1]))
			return 0;

	area = polig_area(polig, n);
	tr_area = 0;

	for (i = 1; i <= n; i++) 
		tr_area = tr_area + abs(det(polig[i], polig[i + 1], p));

	if (tr_area == area)
		return 1;
	return 0;
	
}

int sdet(punct a, punct b, punct c) {
	int t = det(a, b, c);
	if (t < 0)
		return -1;
	if (t > 0)
		return 1;
	return 0;
}

inline int intersect(punct p1, punct p2, punct q1, punct q2) {
	int a, b, c, d;
	int xmin1, xmax1, ymin1, ymax1;
	int xmin2, xmax2, ymin2, ymax2;

	xmin1 = min(p1.x, p2.x);
	xmin2 = min(q1.x, q2.x);
	xmax1 = max(p1.x, p2.x);
	xmax2 = max(q1.x, q2.x);

	ymin1 = min(p1.y, p2.y);
	ymin2 = min(q1.y, q2.y);
	ymax1 = max(p1.y, p2.y);
	ymax2 = max(q1.y, q2.y);

	if (xmax1 < xmin2 || xmax2 < xmin1 || ymax1 < ymin2 || ymax2 < ymin1)
		return 0;

	a = sdet(p1, p2, q1);
	b = sdet(p1, p2, q2);
	c = sdet(q1, q2, p1);
	d = sdet(q1, q2, p2);
	if (a * b * c * d == 0)
		return -1;
	if (a * b == -1 && c * d == -1)
		return 1;
	return 0;
}

inline bool intersection_test(punct p1, punct p2) {
	//la incpeut verific cu laturile, daca se intersecteaza clar atunci las asa si returnez false
	//daca am obtiut vreun 0 pe la determinant atunci bag si testul cu diagonalele
	int i, j, k, verif, val;
	for (i = 1; i <= m; i++) {
		verif = 0;
		for (j = 1; j <= nr_nou[i]; j++) {
			val = intersect(p1, p2, polig_nou[i][j], polig_nou[i][j + 1]); // o sa returnez 1 daca se intersecteaza, 0 daca nu, -1 daca se ating la capat
			if (val > 0) 
				return 0;
		
			if (val < 0)	
				verif = 1;
		}

		if (verif == 1) {
			for (j = 1; j <= nr_nou[i]; j++)
				for (k = j + 1; k <= nr_nou[i]; k++) {
					val = intersect(p1, p2, polig_nou[i][j], polig_nou[i][k]);
					if (val > 0)
						return 0;
				}
		}
	}

	return 1;	
}

inline bool good(punct p1, punct p2) {
	bool ok = 1;
	int i;

	for (i = 1; i <= m; i++) {
		if (point_in_poly(p1, polig_nou[i], nr_nou[i])) 
			ok = 0;

		if (point_in_poly(p2, polig_nou[i], nr_nou[i])) 
			ok = 0;
	
		if (ok == 0) 
			return 0;
	}

	if (intersection_test(p1, p2) == 0) 
		return 0;

	return 1;
}

inline double dist(punct p1, punct p2) {
	return (sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)));
}

inline void make_graph() {
	nr_nou[0] = 2;
	polig_nou[0][1] = start;
	polig_nou[0][2] = stop;

	for (i1 = 0; i1 <= m; i1++)
		for (i2 = 1; i2 <= nr_nou[i1]; i2++)
			for (jj1 = 0; jj1 <= m; jj1++)
				for (jj2 = 1; jj2 <= nr_nou[jj1]; jj2++) {
					p1 = polig_nou[i1][i2];
					p2 = polig_nou[jj1][jj2];
					if (good(p1, p2)) {
						g[i1][i2].push_back(mp(jj1, jj2));
						cst[i1][i2].push_back(dist(polig_nou[i1][i2], polig_nou[jj1][jj2]));
					}
				}
}

void dijkstra(int x, int y) {
	int i, j, ok, ind1, ind2;
	double smin, ct;
	for (i = 0; i <= m; i++)
		for (j = 0; j <= nr_nou[i]; j++)
			cmin[i][j] = 2000000000;
	memset(usd, 0, sizeof(usd));
	cmin[x][y] = 0;

	ok = 1;
	while (ok) {
		ok = 0;
		smin = inf;

		for (i = 0; i <= m; i++)
			for (j = 1; j <= nr_nou[i]; j++)
				if (!usd[i][j] && cmin[i][j] < smin) {
					smin = cmin[i][j];
					x = i; y = j;
					ok = 1;
				}
		
		if (ok == 0)
			break;
		usd[x][y] = 1;

		for (i = 0; i < g[x][y].size(); i++) {
			ind1 = g[x][y][i].first;
			ind2 = g[x][y][i].second;
			ct = cst[x][y][i];

			if (cmin[x][y] + ct < cmin[ind1][ind2]) 
				cmin[ind1][ind2] = cmin[x][y] + ct;
		}
	}
}


int main() {
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);

	scanf("%d", &n);

	ref.x = ref.y = inf;
	for (i = 1; i <= n; i++) {
		
		scanf("%d%d", &robot[i].x, &robot[i].y);
		ref.x = min(ref.x, robot[i].x);
		ref.y = min(ref.y, robot[i].y);
	}
	start = ref;
	robot[n + 1] = robot[1];

	scanf("%d", &m);
	for (i = 1; i <= m; i++) {
		scanf("%d", &nr[i]);
		for (j = 1; j <= nr[i]; j++)
			scanf("%d%d", &polig[i][j].x, &polig[i][j].y);
		polig[i][nr[i] + 1] = polig[i][1];
	}

	scanf("%d%d", &stop.x, &stop.y);

	for (i = 1; i <= m; i++) 
		make_new_polig(i);

	make_graph();
	dijkstra(0, 1);

	printf("%.2lf\n", cmin[0][2]);

	return 0;
}