Cod sursa(job #933050)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 29 martie 2013 15:54:22
Problema Robot Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.58 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;

const int nmax = 15, mmax = 30, pmax = 2505;
int N, M, NR[mmax], O[mmax];
double D[pmax];
struct punct { int x, y; } PI, PF, R[nmax], RD[nmax];
struct nod { int x, y, p; };
vector <punct> A[mmax], AUX, INF;
vector <nod> G;
vector < pair < int, double > > V[pmax];
queue <int> Q;

bool cmp (punct a, punct b)
{
	if (a.y == 0 && b.y == 0) return a.x < b.x;
	if (a.y == 0) return 1;
	if (b.y == 0) return 0;
	if (a.x * b.y == b.x * a.y) return a.x < b.x;
	return a.x * b.y > b.x * a.y;
}

int semn (punct p1, punct p2, punct p3)
{
	return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

double dist (int x1, int y1, int x2, int y2)
{
	return sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool nuseintersecteaza (punct p1, punct p2, punct p3, punct p4)
{
	if (semn (p1, p2, p3) * semn (p1, p2, p4) >= 0)
		return 1;
	if (semn (p3, p4, p1) * semn (p3, p4, p2) >= 0)
		return 1;
	return 0;
}

void citire ()
{
	int i, j;
	punct p;
	
	scanf ("%d", &N);
	
	scanf ("%d%d", &R[1].x, &R[1].y);
	PI.x = R[1].x;
	PI.y = R[1].y;
	for (i = 2; i <= N; i++)
	{
		scanf ("%d%d", &R[i].x, &R[i].y);
		PI.x = min (PI.x, R[i].x);
		PI.y = min (PI.y, R[i].y);
	}
	
	scanf ("%d", &M);
	for (i = 1; i <= M; i++)
	{
		scanf ("%d", &NR[i]);
		O[i] = 0;
		for (j = 0; j < NR[i]; j++)
		{
			scanf ("%d%d", &p.x, &p.y);
			/*
			if (j > 0)
				if (A[i][O[i]].y > p.y || (A[i][O[i]].y == p.y && A[i][O[i]].x > p.x))	
					O[i] = j;
			*/
			A[i].push_back (p);
		}
	}
	
	scanf ("%d%d", &PF.x, &PF.y);
}

void preprocesare ()
{
	R[0] = R[N];
	R[N+1] = R[1];
	
	for (int i = 1; i <= N; i++)
	{
		RD[i].x = R[i].x - PI.x;
		RD[i].y = R[i].y - PI.y;
	}
}

void construieste_start ()
{
	nod ng;
	ng.x = PI.x;
	ng.y = PI.y;
	ng.p = 0;
	G.push_back (ng);	
}

void coliziuni (int n)
{
	//caut punctele care vor forma noul obstacol, adaptat la dimensiunile robotului
	int i, j;
	punct p;
	AUX.clear ();
	
	for (i = 0; i < NR[n]; i++)
	{
		for (j = 1; j <= N; j++)
		{
			p.x = A[n][i].x - RD[j].x;
			p.y = A[n][i].y - RD[j].y;
			
			AUX.push_back (p);
			if (AUX.front().y > AUX.back().y || (AUX.front().y == AUX.back().y && AUX.front().x > AUX.back().x))
			{
				swap (AUX.front(), AUX.back());
			}
		}
	}
}

void infasoara (int n)
{
	if (AUX.size() <= 1)
	{
		INF.push_back (AUX.front ());
		if (AUX.size () == 1)
			INF.push_back (AUX.back ());
		return;	
	}
	
	int i, j;
	punct pmemo;
	vector <punct> :: iterator it;
	INF.clear ();
	
	pmemo = AUX.front();
	for (i = 0; i < AUX.size(); i++)
	{
		AUX[i].x -= pmemo.x;
		AUX[i].y -= pmemo.y;
	}
	
	it = AUX.begin(); it++;
	sort (it, AUX.end(), cmp);
	//AUX.pop_back (pzero);
	
	for (i = AUX.size() - 1; i > 1 && semn (AUX.front(), AUX[i], AUX[i-1]) == 0; i--);
	for (j = AUX.size() - 1; i < j; i++, j--) swap (AUX[i], AUX[j]);
	
	INF.push_back (AUX[0]);
	INF.push_back (AUX[1]);
	INF.push_back (AUX[2]);
	
	for (i = 3; i < AUX.size(); i++)
	{
		while (INF.size () > 1 && semn (INF[INF.size() - 2], INF.back(), AUX[i]) <= 0)
			INF.pop_back ();
		INF.push_back (AUX[i]);
	}
	
	for (i = 0; i < INF.size(); i++)
	{
		INF[i].x += pmemo.x;
		INF[i].y += pmemo.y;
	}
}

void reconstruieste (int n)
{
	nod ng;
	double c;
	int i, j;
	A[n].clear ();
	
	for (i = j = G.size(); !INF.empty (); j++)
	{
		ng.x = INF.back().x;
		ng.y = INF.back().y;
		ng.p = n;
		/*
		if (i != G.size())
		{
			c = dist (G.back().x, G.back().y, ng.x, ng.y);
			V[j-1].push_back (make_pair (j, c));
			V[j].push_back (make_pair (j-1, c));
		}
		*/
		G.push_back (ng);
		A[n].push_back (INF.back ());
		INF.pop_back ();
	}
	j--;
	/*
	c = dist (G[i].x, G[i].y, G[j].x, G[j].y);
	V[i].push_back (make_pair (j, c));
	V[j].push_back (make_pair (j, c));	
	*/
	A[n].push_back (A[n].front());
}

void construieste_finish ()
{
	nod ng;
	ng.x = PF.x;
	ng.y = PF.y;
	ng.p = M + 1;
	G.push_back (ng);	
}

void fa_graf ()
{
	int i, j, n, k;
	double c;
	punct p1, p2, p3, p4;
	bool ok;
	
	construieste_start ();
	for (i = 1; i <= M; i++)
	{
		coliziuni (i);
		infasoara (i);
		reconstruieste (i);
	}
	construieste_finish ();
	
	for (i = 1; i < G.size(); i++)
	{
		p1.x = G[i].x;
		p1.y = G[i].y;
		
		for (j = 0; j < i; j++)
		{
			if (G[i].p == G[j].p)
				if ( !( (j == i - 1) || (G[j-1].p != G[j].p && G[i].p != G[i+1].p) ) )
					continue;
			
			ok = 1;
			p2.x = G[j].x;
			p2.y = G[j].y;
			
			for (n = 1; n <= M && ok; n++)
			{
				for (k = 1; k < A[n].size() && ok; k++)
				{
					p3.x = A[n][k-1].x;
					p3.y = A[n][k-1].y;
					
					p4.x = A[n][k].x;
					p4.y = A[n][k].y;
					
					ok &= nuseintersecteaza (p1, p2, p3, p4);
				}
			}
			if (ok == 0) continue;
			
			c = dist (p1.x, p1.y, p2.x, p2.y);
			V[i].push_back (make_pair (j, c));
			V[j].push_back (make_pair (i, c));	
		}
	}
}

void bellman_ford ()
{
	int n, f, i;
	double c;
	
	Q.push (0);
	for (i = 0; i < G.size(); i++)
	{
		D[i] = -1;
	}
	D[0] = 0;
	
	while (!Q.empty())
	{
		n = Q.front ();
		Q.pop ();
		
		for (i = 0; i < V[n].size(); i++)
		{
			f = V[n][i].first;
			c = V[n][i].second;
			
			if (D[f] == -1 || D[f] > D[n] + c)
			{
				D[f] = D[n] + c;
				Q.push (f);
			}
		}
	}
	
	printf ("%.2lf\n", D[G.size() - 1]);
}

int main ()
{
	freopen ("robot.in", "r", stdin);
	freopen ("robot.out", "w", stdout);
	
	citire ();
	preprocesare ();
	fa_graf ();
	bellman_ford ();
	
	return 0;
}