Cod sursa(job #356398)

Utilizator savimSerban Andrei Stan savim Data 14 octombrie 2009 18:17:06
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.19 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAX_N 512
#define inf 100000

int n, m, k, X, Y, Xfin, Yfin;
int len[MAX_N], use[MAX_N];
double d[MAX_N][MAX_N], c[MAX_N];

struct punct {
	int x, y;
} v[MAX_N][MAX_N], R[MAX_N], P[MAX_N];
struct segment {
    int x1, y1, x2, y2;
} aux[MAX_N];
                         
void cit() {
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);

	X = Y = inf;

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &R[i].x, &R[i].y);
		X = min(X, R[i].x); Y = min(Y, R[i].y);
	}

	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
    	scanf("%d", &len[i]);
		for (int j = 1; j <= len[i]; j++)
			scanf("%d %d", &v[i][j].x, &v[i][j].y);
	}
	scanf("%d %d", &Xfin, &Yfin);
}

inline int next(int k, int n) {
	if ((k + 1) % n) return (k + 1) % n;
	else return n;
}

inline int prec(int k, int n) {
	if (k - 1 > 0) return k - 1;
	else return n;
}

inline int cmp(segment P, segment Q) {
	return atan2((P.y2 - P.y1) , (P.x2 - P.x1)) < atan2((Q.y2 - Q.y1) , (Q.x2 - Q.x1));
}

void polig_build(int el) {
	//p, q - punctul din stanga jos al poligonului ce trebuie extins
	int p = inf, q = inf;
	for (int i = 1; i <= len[el]; i++)
		if (v[el][i].x < p || (v[el][i].x == p && v[el][i].y < q)) {
        	p = v[el][i].x;
			q = v[el][i].y;
		}

	//r, t - punctul din dreapta sus al robotului
	int r = -inf, t = -inf;
	for (int i = 1; i <= n; i++)
		if ((R[i].x > r) || (R[i].x == r && R[i].y > t)) {
        	r = R[i].x;
			t = R[i].y;
		}

	//calculez mx, my : coordonatele punctului din stanga jos al poligonului rezultat	
	int mx = p - (r - X);
	int my = q - (t - Y);

	len[el] = k;
	for (int i = 1; i <= len[el]; i++) {
		v[el][k - i + 1].x = aux[i].x2 - aux[i].x1;
		v[el][k - i + 1].y = aux[i].y2 - aux[i].y1;
	}

	//gasesc cel mai din stanga - jos element al poligonului rezultat
	p = q = inf;
	int st = 0, dr = 0, poz = 0;
	for (int i = 1; i <= len[el]; i++) {
    	st += v[el][i].x; dr += v[el][i].y;

		if ((st < p) || (st == p && dr < q)) {
			poz = i;
			p = st; q = dr;
		}
	}

	//calculez noul poligon
	v[el][poz].x = mx; v[el][poz].y = my;
	for (int i = 1; i <= len[el] - 1; i++) {
		int nxtp = next(poz, len[el]);

		v[el][nxtp].x += v[el][poz].x; 
		v[el][nxtp].y += v[el][poz].y;

		poz = nxtp;
	}
}

void expand() {
	//iau robotelul in sens trigonometric, si obstacolele in sens invers trigonometric
	for (int i = 1; i <= m; i++) {
		k = 0;
		if (n - 1) {
			for (int j = 1; j <= n; j++) {
				aux[j].x1 = R[j].x; aux[j].x2 = R[next(j, n)].x;
				aux[j].y1 = R[j].y; aux[j].y2 = R[next(j, n)].y;
			}
			k = n;
		}

		if (len[i] - 1) 
			for (int j = 1; j <= len[i]; j++) {
        		k++;
				aux[k].x1 = v[i][j].x; aux[k].x2 = v[i][prec(j, len[i])].x;
				aux[k].y1 = v[i][j].y; aux[k].y2 = v[i][prec(j, len[i])].y;
			}

		sort(aux + 1, aux + k + 1, cmp);

		//construiesc poligonul marit, parcurgand segmentele in ordinea n, n - 1 .. 1
		polig_build(i);
	}
}

inline int det(punct A, punct B, punct C) {
	return A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - B.x * A.y - C.x * B.y;
}

inline int intersect(punct A, punct B, punct P, punct Q) {
	long long p1 = 1LL * det(A, P, Q) * det(B, P, Q);
	long long p2 = 1LL * det(P, A, B) * det(Q, A, B);

	if (p1 < 0 && p2 < 0) return 1;
	return 0;
}

bool point_ok(int x, int y) {
	for (int i = 1; i <= m; i++)
    	for (int j = 1; j < len[i]; j++)
			for (int k = j + 1; k <= len[i]; k++)
				if (intersect(P[x], P[y], v[i][j], v[i][k]))
					return false;
	return true;
}

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

void point_in_poly() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			v[j][len[j] + 1] = v[j][1];

        	int find = 1;
			for (int k = 1; k <= len[j]; k++)
				if (det(P[i], v[j][k], v[j][k + 1]) == 0) {
                	find = 0;
					break;
				}

			if (find) {
            	int S1 = 0, S2 = 0;
				for (int k = 1; k <= len[j]; k++) {
					S1 = S1 + v[j][k].x * v[j][k + 1].y - v[j][k + 1].x * v[j][k].y;
					S2 = S2 + abs(det(P[i], v[j][k], v[j][k + 1]));
				}
				
				S1 = abs(S1);
				if (S1 == S2 && S1) {
					use[i] = 1;
					break;
				}
			}
		}
}

void make_graph() {
	n = 1; P[1].x = X; P[1].y = Y;
	for (int i = 1; i <= m; i++)
    	for (int j = 1; j <= len[i]; j++)
			P[++n] = v[i][j];
	n++; P[n].x = Xfin; P[n].y = Yfin;

	//vad ce puncte sunt incluse in poligoane
	point_in_poly();

	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
			if (point_ok(i, j) && !use[i] && !use[j])
				d[i][j] = d[j][i] = dist(P[i], P[j]);
}

void dijkstra() {
	for (int i = 2; i <= n; i++)
		c[i] = -1;
			
	for (int i = 1; i < n; i++) {
    	int minim = inf, poz = 0;

		for (int j = 1; j <= n; j++)
			if (c[j] >= 0 && c[j] < minim && use[j] == 0) {
            	minim = c[j];
				poz = j;
			}

		if (minim == inf) break;

		use[poz] = 1;
		for (int j = 1; j <= n; j++)
			if (d[poz][j] && (c[poz] + d[poz][j] < c[j] || c[j] < 0))
				c[j] = c[poz] + d[poz][j];
	}

	printf("%.2lf\n", c[n]);
}

void solve() {
	//maresc obstacolele	
	expand();

	//construiesc graful pentru dijkstra
	make_graph();

	//aplic algoritmul lui dijkstra(N ^ 2) in graful rezultat
	dijkstra();
}

int main() {

	cit();
	solve();

	return 0;
}