Cod sursa(job #72103)

Utilizator wefgefAndrei Grigorean wefgef Data 12 iulie 2007 18:42:07
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.18 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define punct pair<int, int>
#define punct2 pair<double, double>
#define tr(c, it) for (typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()

#define inf 1e9
#define Pmax 30000

punct finish;
vector< punct > robot;
vector< vector< punct> > obstacol;

char viz[Pmax];
int st[Pmax];

vector< punct > v;
punct2 inter;

void readdata()
{
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);

	int i, j, a, b, n, m;
	vector<punct> aux;

	scanf("%d", &n);
	for (i = 0; i < n; ++i)
	{
		scanf("%d %d", &a, &b);
		robot.pb( mp(a, b) );
	}

	scanf("%d", &m);
	for (i = 1; i <= m; ++i)
	{
		scanf("%d", &n);
		for (aux.clear(), j = 0; j < n; ++j)
		{
			scanf("%d %d", &a, &b);
			aux.pb( mp(a, b) );
		}
		obstacol.pb(aux);
	}

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

int sign(punct a, punct b, punct c)
{
	int prod = (a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y);
	return (prod == 0 ? 0 : prod < 0 ? -1 : 1);
}

void convex_hull(vector< punct > &v)
{
	int i, p = 1, n;
	vector< punct> aux;

	sort( all(v) );
	v.resize( unique(all(v)) - v.begin() );

	n = sz(v);
	memset(viz, 0, sizeof(viz));
	st[ st[0] = 1 ] = 0;
	for (i = 1; i >= 0; i += (p = (i == n-1) ? -p : p))
		if (!viz[i])
		{
			while (st[0] >= 2 && sign(v[i], v[st[ st[0] ]], v[st[ st[0]-1 ]]) <= 0)
					viz[ st[ st[0]-- ] ] = 0;
			viz[ st[++st[0]] = i ] = 1;
		}
	for (i = 1; i < st[0]; ++i)
		aux.pb(v[st[i]]);
	v = aux;
}

void refa_obstacol(vector< punct > &v)
{
	int i, j, lim = sz(v);
	
	for (i = 0; i < lim; ++i)
		for (j = 0; j < sz(robot); ++j)
			v.pb( mp(v[i].x + robot[0].x - robot[j].x, v[i].y + robot[0].y - robot[j].y) );
	convex_hull(v);
}

void refa_finish()
{
	int best = robot[0].y;
	tr(robot, it) best = min(best, it->y);
	finish.y += robot[0].y-best;
}

inline double sqr(int a) { return double(a*a); }

int apartine(punct a, punct b, punct c)
{
	punct p1 = min(b, c), p2 = max(b, c);

	return ((a.y-p1.y)*(p2.x-p1.x) == (a.x-p1.x)*(p2.y-p1.y) && a >= p1 && a <= p2);
}

int coliniar(punct a, punct b, punct c)
{
	return (a.y-b.y)*(c.x-b.x) == (a.x-b.x)*(c.y-b.y);
}

int contur(punct a, vector< punct > &v)
{
	for (int i = 0; i < sz(v)-1; ++i)
		if (apartine(a, v[i], v[i+1]))
			return 1;
	return 0;
}

int arie_poligon(vector< punct > &v)
{
	int ret = 0, i;
	for (i = 0; i < sz(v)-1; ++i)
		ret += v[i].x*v[i+1].y - v[i+1].x*v[i].y;
	return abs(ret);
}

int arie_punct(punct a, vector< punct > &v)
{
	vector< punct > aux;
	int ret = 0, i;

	for (i = 0; i < sz(v)-1; ++i)
	{
		aux.clear();
		aux.pb(v[i]), aux.pb(v[i+1]), aux.pb(a); aux.pb(v[i]);
		ret += arie_poligon(aux);
	}
	return ret;
}

int intersection(punct a, punct b, punct c, punct d)
{
	double A, B, C, A2, B2, C2, det;

	A = b.y-a.y;
	B = a.x-b.x;
	C = -a.y*(b.x-a.x) + a.x*(b.y-a.y);

	A2 = d.y-c.y;
	B2 = c.x-d.x;
	C2 = -c.y*(d.x-c.x) + c.x*(d.y-c.y);

	det = A*B2 - B*A2;
	if (det == 0) return 0;
	inter = mp( (B2*C - B*C2)/det, (A*C2 - A2*C)/det );

	return (sign(c, b, a) * sign(d, b, a) <= 0 && sign(a, c, d) * sign(b, c, d) <= 0);
}

int intersecteaza(punct a, punct b, vector< punct > &v)
{
	int i;

	//cazul in care a si b apartin dreptei suport a unei laturi
	for (i = 0; i < sz(v)-1; ++i)
		if (coliniar(a, v[i], v[i+1]) && coliniar(b, v[i], v[i+1]))
			return 0;

	//afla care din puncte se afla pe conturul poligonului
	char v1 = contur(a, v), v2 = contur(b, v);
	if (v1 && v2) return 1;

	//cazul in care un punct apartine interiorului poligonului
	int ap = arie_poligon(v), a1 = arie_punct(a, v), a2 = arie_punct(b, v);
	if (a1 == ap && !v1) return 1;
	if (a2 == ap && !v2) return 1;

	vector< punct2 > aux;
	for (i = 0; i < sz(v)-1; ++i)
		if (intersection(a, b, v[i], v[i+1]))
			aux.pb(inter);
	sort(all(aux));
	aux.resize( unique(all(aux)) - aux.begin() );

	return sz(aux) > 1;
}

double afla_distanta(punct a, punct b)
{
	double ret = sqrt(sqr(a.x-b.x) + sqr(a.y-b.y));
	int i;

	if (a == b) return ret;
	for (i = 0; i < sz(obstacol); ++i)
		if (intersecteaza(a, b, obstacol[i]))
			return inf;
	return ret;
}

void solve()
{
	int i, j;

	//redu robotul la un singur punct;
	sort(all(robot));
	for (i = 0; i < sz(obstacol); ++i)
		refa_obstacol(obstacol[i]);
	refa_finish();

	//afla punctele ce pot fi vizitate si matricea de adiacenta
	v.pb(robot[0]);
	for (i = 0; i < sz(obstacol); ++i)
		for (j = 0; j < sz(obstacol[i]); ++j)
			v.pb(obstacol[i][j]);
	v.pb(finish);

	vector< vector< double > > c( sz(v), sz(v) );

	for (i = 0; i < sz(obstacol); ++i)
		obstacol[i].pb( obstacol[i][0] );

	for (i = 0; i < sz(v); ++i)
		for (j = 0; j < sz(v); ++j)
			c[i][j] = afla_distanta(v[i], v[j]);

	//afla drumul cel mai scurt si afiseaza
	int n = sz(v)-1;
	vector< double > d(n+1, inf);
	vector< char > viz(n+1, 0);

	double best;
	int poz;

	d[0] = 0;
	while (!viz[n])
	{
		best = inf;
		for (i = 0; i <= n; ++i)
			if (!viz[i] && d[i] < best)
			{
				best = d[i];
				poz = i;
			}
		viz[poz] = 1;
		for (i = 0; i <= n; ++i)
			d[i] = min(d[i], best + c[poz][i]);
	}
	printf("%lf\n", d[n]);
}

int main()
{
	readdata();
	solve();
	return 0;
}