Cod sursa(job #364864)

Utilizator tvladTataranu Vlad tvlad Data 17 noiembrie 2009 10:07:02
Problema Robot Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.79 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int N_MAX = 11;
const int M_MAX = 26;
const int V_MAX = 256;
const int INF = 0x3f3f3f3f;

typedef unsigned int uint;

int sign ( int x ) { return x < 0 ? -1 : !!x; }

struct punct {
	int x, y;
	punct() {};
	punct ( int X, int Y ) { x = X; y = Y; };
};
bool operator< ( punct a, punct b ) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
punct operator+ ( punct a, punct b ) { return punct(a.x + b.x, a.y + b.y); }
punct operator- ( punct a, punct b ) { return punct(a.x - b.x, a.y - b.y); }
double dist ( punct a, punct b ) { return sqrt((double)(a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); }

punct O, dest;

struct segment {
	punct a, b;
	segment() {};
	segment ( punct A, punct B ) { a = A; b = B; };
};
bool operator< ( const segment &a, const segment &b ) { return atan2((double)a.b.y - a.a.y, a.b.x - a.a.x) < atan2((double)b.b.y - b.a.y, b.b.x - b.a.x); }
inline int det ( punct a, punct b, punct c ) { return a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y; }
bool on_segment ( punct p, punct a, punct b ) {
	int xmin = min(a.x, b.x);
	int xmax = max(a.x, b.x);
	int ymin = min(a.y, b.y);
	int ymax = max(a.y, b.y);
	return det(a,b,p) == 0 && xmin <= p.x && p.x <= xmax && ymin <= p.y && p.y <= ymax;
}
int intersectie ( punct a, punct b, punct c, punct d ) {
	int xmin1 = min(a.x, b.x), xmax1 = max(a.x, b.x), ymin1 = min(a.y, b.y), ymax1 = max(a.y, b.y);
	int xmin2 = min(c.x, d.x), xmax2 = max(c.x, d.x), ymin2 = min(c.y, d.y), ymax2 = max(c.y, d.y);
	if (xmax1 < xmin2 || xmax2 < xmin1 || ymax1 < ymin2 || ymax2 < ymin1) return 0;
	int s1 = sign(det(a,b,c)), s2 = sign(det(a,b,d)), s3 = sign(det(c,d,a)), s4 = sign(det(c,d,b));
	if (s1*s2*s3*s4 == 0) return -1;
	return s1*s2 == -1 && s3*s4 == -1;
}

struct poligon {
	int sz;
	poligon() { sz = 0; };
	punct v[V_MAX];
	punct& operator[] ( int k ) { return v[k]; }
	void read() {
		scanf("%d",&sz);
		for (int i = 0; i < sz; ++i) scanf("%d %d",&v[i].x,&v[i].y);
		v[sz] = v[0];
	};
	void push ( punct x ) {
		v[sz] = x;
		v[++sz] = v[0];
	};
	punct max() {
		punct mx(0,0);
		for (int i = 0; i < sz; ++i) {
			if (mx < v[i])
				mx = v[i];
		}
		return mx;
	};
	punct min() {
		punct mn(INF,INF);
		for (int i = 0; i < sz; ++i)
			if (v[i] < mn)
				mn = v[i];
		return mn;
	};
	punct referinta() {
		punct o(INF, INF);
		for (int i = 0; i < sz; ++i) {
			if (o.x > v[i].x)
				o.x = v[i].x;
			if (o.y > v[i].y)
				o.y = v[i].y;
		}
		return o;
	};
	int area() {
		int sum = 0;
		for (int i = 0; i < sz; ++i)
			sum += v[i].x * v[i+1].y - v[i].y * v[i+1].x;
		return sum;
	}
	void move ( int dx, int dy ) {
		for (int i = 0; i <= sz; ++i)
			v[i].x += dx, v[i].y += dy;
	};
	void move ( punct d ) { move(d.x, d.y); };
	void extend ( poligon &p ) {
		vector<segment> vs;
		for (int i = 0; i < sz; ++i) vs.push_back(segment(v[i], v[i+1]));
		for (int i = p.sz; i > 0; --i) vs.push_back(segment(p[i],p[i-1]));
		sort(vs.begin(), vs.end());
		
		punct cur(0,0);
		poligon nou;
		for (uint i = 0; i < vs.size(); ++i) {
			nou.push(cur);
			cur = cur + vs[i].b - vs[i].a;
		}

		punct dif = O + min() - p.max() - nou.min();
		nou.move(dif);
		sz = nou.sz;
		for (int i = 0; i <= sz; ++i)
			v[i] = nou[i];
	};
};
bool operator< ( punct &a, poligon &p ) {
	for (int i = 0; i < p.sz; ++i)
		if (on_segment(a, p[i], p[i+1]))
			return false;
	int ar_a = 0;
	for (int i = 0; i < p.sz; ++i)
		ar_a += (int)fabs((double)det(p[i], p[i+1], a));
	return ar_a == p.area();
}

poligon rbt;
int n;
poligon obs[M_MAX];
vector< pair< pair<int,int>, double > > G[M_MAX][V_MAX];
double dij[M_MAX][V_MAX];
bool used[M_MAX][V_MAX];

bool ok ( punct a, punct b ) {
	for (int i = 0; i < n; ++i)
		if (a < obs[i] || b < obs[i])
			return false;
	// testez ca (a,b) sa nu se intersecteze cu vreun obstacol, mai intai cu laturile si dupa aia daca primesc ca se pupa-n varf, cu diagonalele
	for (int i = 0; i < n; ++i) {
		bool diag = false;
		for (int j = 0; j < obs[i].sz; ++j) {
			int cross = intersectie(a, b, obs[i][j], obs[i][j+1]);
			if (cross == -1) diag = true;
			if (cross == 1) return false;
		}
		if (diag)
			for (int j = 0; j < obs[i].sz; ++j)
				for (int k = j+1; k < obs[i].sz; ++k)
					if (intersectie(a, b, obs[i][j], obs[i][k]) == 1)
						return false;
	}
	return true;
}

void build_graph() {
	obs[n].push(O);
	obs[n].push(dest);
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j < obs[i].sz; ++j)
			for (int k = 0; k <= n; ++k)
				for (int t = 0; t < obs[k].sz; ++t)
					if (ok(obs[i][j], obs[k][t]))
						G[i][j].push_back(make_pair(make_pair(k, t), dist(obs[i][j], obs[k][t])));
}

void dijkstra ( int sx, int sy ) {
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j < obs[i].sz; ++j)
			dij[i][j] = INF;
	dij[sx][sy] = 0;
	while (true) {
		double dmin = INF;
		int x = INF, y = INF;
		for (int i = 0; i <= n; ++i)
			for (int j = 0; j < obs[i].sz; ++j)
				if (!used[i][j] && dij[i][j] < dmin)
					dmin = dij[i][j], x = i, y = j;
		if (dmin == INF)
			break;
		used[x][y] = true;
		int nx, ny;
		double cost;
		for (uint i = 0; i < G[x][y].size(); ++i) {
			nx = G[x][y][i].first.first;
			ny = G[x][y][i].first.second;
			cost = G[x][y][i].second;
			if (dij[x][y] + cost < dij[nx][ny])
				dij[nx][ny] = dij[x][y] + cost;
		}
	}
}

int main() {
	freopen("robot.in","rt",stdin);
	freopen("robot.out","wt",stdout);
	printf("-1\n");
	return 0;
	rbt.read();
	O = rbt.referinta();
	scanf("%d",&n);
	for (int i = 0; i < n; ++i) {
		obs[i].read();
		obs[i].extend(rbt);
	}
	scanf("%d %d",&dest.x,&dest.y);
	build_graph();
	dijkstra(n,0);
	if (dij[n][1] == INF)
		printf("-1\n"); else
		printf("%.3lf\n",dij[n][1]);
	return 0;
}