Cod sursa(job #32526)

Utilizator gcosminGheorghe Cosmin gcosmin Data 17 martie 2007 23:21:01
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.27 kb
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define NMAX 50
#define MMAX 50
#define INF 1000000000
#define MP make_pair

inline int MIN(int a, int b) { return (a < b) ? a : b; }
inline int MAX(int a, int b) { return (a > b) ? a : b; }
inline int ABS(int x) { return (x < 0) ? -x : x; }

int N, M;

int P[MMAX];
pair <int, int> rob[NMAX];
vector <pair<int, int> > obs[MMAX];
vector <pair<int, int> > obs1[MMAX];
vector <pair<int, int> > OBS[MMAX];
int NOBS[MMAX];
int arie[NMAX];

vector <pair<int, int> > pct;

char viz[250 * NMAX * NMAX];

int st[250 * NMAX * NMAX];

vector <pair<int, double> > leg[250 * NMAX];

double dst[250 * NMAX];

set <pair<double, int> > H;

int semn(pair <int, int> a, pair <int, int> b, pair <int, int> c)
{
	int q = a.first * (b.second - c.second) - a.second * (b.first - c.first) + b.first * c.second - b.second * c.first;
	if (q < 0) return -1;
	if (q > 0) return 1;
return 0;
}

int ARIE(pair <int, int> a, pair<int, int> b, pair<int, int> c)
{
	return a.first * (b.second - c.second) - a.second * (b.first - c.first) + b.first * c.second - b.second * c.first;
}

void make_hull(int x)
{
	int N = 0;

	sort(obs1[x].begin(), obs1[x].end());

	vector <pair<int, int> > :: iterator it = unique(obs1[x].begin(), obs1[x].end());

	while (it != obs1[x].begin()) N++, --it;

	memset(viz, 0, sizeof(viz));

	int p = 1, i;

	st[0] = 1;
	st[1] = 0;

	for (i = 1; i >= 0; i += (p = (i == N - 1 ? -p : p)))
		if (!viz[i]) {
			while (st[0] >= 2 && semn(obs1[x][i], obs1[x][ st[ st[0] - 1 ] ], obs1[x][ st[ st[0] ] ]) < 0) viz[ st[ st[0]-- ] ] = 0;
			viz[ st[ ++st[0] ] = i] = 1;
		}

	for (i = 1; i <= st[0]; i++) {
		if (1 < i && i < st[0] && !semn( obs1[x][ st[i - 1] ], obs1[x][ st[i] ], obs1[x][ st[i+1] ])) continue;
		OBS[x].push_back(obs1[x][ st[i] ]);
	}
	NOBS[x] = OBS[x].size();

	for (i = 0; i < NOBS[x] - 1; i++) arie[x] += OBS[x][i].first * OBS[x][i+1].second - OBS[x][i].second * OBS[x][i+1].first;
	arie[x] = ABS(arie[x]);
}

double dist(pair <int, int> a, pair <int, int> b)
{
	return sqrt( (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) );
}

int intersect(pair <int, int> a, pair <int, int> b, pair <int, int> c, pair <int, int> d)
{
	return semn(a, c, d) * semn(b, c, d) == -1 && semn(c, a, b) * semn(d, a, b) == -1;
}

int pe_dreapta(pair <int, int> a, pair<int, int> b, pair<int, int> c)
{
	return MIN(b.first, c.first) <= a.first && a.first <= MAX(b.first, c.first) && MIN(b.second, c.second) <= a.second && a.second <= MAX(b.second, c.second);
}

int punct_in_pol(pair <int, int> a, int x)
{
	int i, ar = 0, q;

	for (i = 0; i < NOBS[x] - 1; i++) {
		q = ARIE(a, OBS[x][i], OBS[x][i+1]);
		if (!q && pe_dreapta(a, OBS[x][i], OBS[x][i+1])) return i + 5;
		ar += ABS(q);
	}

	if (ar == arie[x]) return 1;
return 0;
}

int verif_jeg(pair<int, int> a, pair<int, int> b, int x)
{
	int i, q, pp = -1;

	for (i = 0; i < NOBS[x] - 1; i++) {
		q = semn(OBS[x][i], a, b);
		if (!q && pe_dreapta(OBS[x][i], a, b)) {
			if (pp == -1) pp = i;
			else if (!( pp == i - 1 || pp == 0 && i == NOBS[x] - 2)) return 0;
		}
	}
	
return 1;
}

int verif_jeg2(pair<int, int> a, pair<int, int> b, int x)
{
	int i, q, w, pa = -1, pb = -1, apa = -1, apb = -1;

	for (i = 0; i < NOBS[x] - 1; i++) {
		q = semn(a, OBS[x][i], OBS[x][i+1]);
		w = semn(b, OBS[x][i], OBS[x][i+1]);
		if (!q && !w) return 1;
		
		if (a == OBS[x][i]) pa = i;
		if (b == OBS[x][i]) pb = i;

		if (!q && pe_dreapta(a, OBS[x][i], OBS[x][i+1])) apa = i;
		if (!w && pe_dreapta(b, OBS[x][i], OBS[x][i+1])) apb = i;
	}

	if (pa != -1 && pb != -1) {
		if (! (pa == pb + 1 || pb == pa + 1)) return 0;
		return 1;
	}

	if (pa != -1) {
		if (apb != -1) {
			if (! (pa == apb || pa - 1 == apb)) return 0;
			return 1;
		}
		return 1;
	}

	if (pb != -1) {
		if (apa != -1) {
			if (! (pb == apa || pb - 1 == apa)) return 0;
			return 1;
		}
		return 1;
	}

	if (apa != -1 && apb != -1 && apa != apb) return 0;
	
return 1;
}

int seg_bun(pair <int, int> a, pair <int, int> b)
{
	int i, j, e1, e2;

	if (a == b) return 1;

	for (i = 1; i <= M; i++) {
		e1 = punct_in_pol(a, i);
		e2 = punct_in_pol(b, i);
		if (e1 == 1 || e2 == 1) return 0;

/*		if (e1 > 1 && e2 > 1) {
			if (! (e1 == e2 + 1 || e2 == e1 + 1)) return 0;
		}
*/
		if (!verif_jeg(a, b, i)) return 0;
		if (!verif_jeg2(a, b, i)) return 0;
		for (j = 0; j < NOBS[i] - 1; j++)
			if (intersect(a, b, OBS[i][j], OBS[i][j+1])) return 0;
	}
	
return 1;
}

int pred[250 * NMAX];

int main()
{
	int px, py, i, j, k, x, y, dx, dy, finx, finy;
	
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);

	scanf("%d", &N);

	px = 5000; py = 5000;
	for (i = 1; i <= N; i++) {
		scanf("%d %d", &rob[i].first, &rob[i].second);	
		px = MIN(px, rob[i].first);
		py = MIN(py, rob[i].second);
	}

	scanf("%d", &M);

	for (i = 1; i <= M; i++) {
		scanf("%d", &P[i]);
		for (j = 1; j <= P[i]; j++) {
			scanf("%d %d", &x, &y);
			obs[i].push_back(MP(x, y));
		}
	}

	scanf("%d %d", &finx, &finy);

	// ingras obstacolele

	for (i = 1; i <= M; i++) {
		for (j = 0; j < P[i]; j++) {
			for (k = 1; k <= N; k++) {
				dx = obs[i][j].first - rob[k].first;
				dy = obs[i][j].second - rob[k].second;
				obs1[i].push_back(MP( px + dx, py + dy) );
			}
		}

		make_hull(i);
	}

/*	for (i = 1; i <= M; i++) {
		for (j = 0; j < (int) OBS[i].size(); j++) printf("%d %d | ", OBS[i][j].first, OBS[i][j].second);
		printf("\n");
	}
	printf("\n");
*/
	pct.push_back(MP(px, py));
	for (i = 1; i <= M; i++) {
		for (vector <pair<int,int> > :: iterator it = OBS[i].begin(); it != OBS[i].end(); ++it) pct.push_back(*it);
	}
	pct.push_back(MP(finx, finy));

	// construiesc graful

	int q = pct.size();

	for (i = 0; i < q; i++)
		for (j = i + 1; j < q; j++) {
			if (seg_bun(pct[i], pct[j])) {
				leg[i].push_back(MP(j, dist(pct[i], pct[j])));
				leg[j].push_back(MP(i, dist(pct[i], pct[j])));
			}
		}

/*	for (i = 0; i < q; i++) {
		printf("%d %d | ", pct[i].first, pct[i].second);
		for (vector <pair<int, double> > :: iterator it = leg[i].begin(); it != leg[i].end(); ++it) printf("%d %d - ", pct[(*it).first].first, pct[(*it).first].second);
		printf("\n");
	}
*/
	dst[0] = 0;
	for (i = 1; i < q; i++) dst[i] = INF;

	for (i = 0; i < q; i++) H.insert(MP(dst[i], i));

	vector <pair<int, double> > :: iterator it;

	double cst;

	while (!H.empty()) {
		x = (*H.begin()).second;
		H.erase(*H.begin());

		for (it = leg[x].begin(); it != leg[x].end(); ++it) {
			y = (*it).first;
			cst = (*it).second;
			if (dst[x] + cst < dst[y]) {
				pred[y] = x;
				H.erase(MP(dst[y], y));
				dst[y] = dst[x] + cst;
				H.insert(MP(dst[y], y));
			}
		}
	}

	if (dst[q-1] == INF) { printf("-1\n"); return 0; }

	printf("%0.2lf\n", dst[q - 1]);

/*	int cur = q - 1;
	while (cur) {
		printf("%d %d\n", pct[cur].first, pct[cur].second);
		cur = pred[cur];
	}

	printf("%lf\n", dist(MP(-6, -9), MP(-1, -10)) + dist(MP(-1, -10), MP(1, -8)) + dist(MP(1, -8), MP(2, -6)) + dist(MP(2, -6), MP(5, 4)) + dist(MP(5, 4), MP(5, 7)) + dist(MP(5, 7), MP(-1, 9)) + dist(MP(-1, 9), MP(-3, 8)) + dist(MP(-3, 8), MP(-4, 5)) + dist(MP(-4, 5), MP(-4, 0)));

	printf("%lf\n", dist(MP(-6, -9), MP(-10, -3)) + dist(MP(-10, -3), MP(-12, 1)) + dist(MP(-12, 1), MP(-11, 4)) + dist(MP(-11, 4), MP(-9, 8)) + dist(MP(-9, 8), MP(-6, 7)) + dist(MP(-6, 7), MP(-4, 4)) + dist(MP(-4, 4), MP(-4, 0)));
*/

fclose(stdin);
fclose(stdout);
return 0;
}