Cod sursa(job #933119)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 29 martie 2013 17:11:13
Problema Robot Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.55 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

const int nmax = 15, mmax = 30, pmax = 2505;
int N, M, NR[mmax], O[mmax], ariepoly[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;
bitset <pmax> valid;

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;
}

double absd (double a)
{
	if (a < 0) return -a;
	return a;
}

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 arie (punct p1, punct p2, double x3, double y3)
{
	return absd ((p2.x - p1.x) * (y3 - p1.y) - (x3 - 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;
		
		G.push_back (ng);
		A[n].push_back (INF.back ());
		INF.pop_back ();
	}
	j--;

	A[n].push_back (A[n].front());
	
	for (i = 2; i < A[n].size() - 1; i++)
	{
		ariepoly[n] += abs (semn (A[n].front(), A[n][i-1], A[n][i]));
	}
}

void construieste_finish ()
{
	int i, n, k, arie1;
	bool ok;
	nod ng;
	punct p1;
	
	ng.x = PF.x;
	ng.y = PF.y;
	ng.p = M + 1;
	G.push_back (ng);
	
	valid[0] = 1;
	for (i = 1; i < G.size(); i++)
	{
		ok = 1;
		p1.x = G[i].x;
		p1.y = G[i].y;
		
		for (n = 1; n <= M; n++)
		{
			if (G[i].p == n) continue;
			arie1 = 0;
			
			for (k = 1; k < A[n].size(); k++)
			{
				if (semn (p1, A[n][k-1], A[n][k]) == 0)
				{
					arie1 = -1;
					break;
				}
				arie1 += absd(semn (p1, A[n][k-1], A[n][k]));
			}
			
			if (arie1 == ariepoly[n])
			{
				ok = 0;
				break;
			}
		}
		valid[i] = ok;
	}
}

void fa_graf ()
{
	int i, j, n, k, nrpoz, nrneg, arie1, arie2, arie3;
	double c, xm, ym, aried;
	punct p1, p2, p3, p4;
	bool ok, apartine_latura;
	
	construieste_start ();
	for (i = 1; i <= M; i++)
	{
		coliziuni (i);
		infasoara (i);
		reconstruieste (i);
	}
	construieste_finish ();
	
	for (i = 1; i < G.size(); i++)
	{
		if (valid[i] == 0) continue;
		p1.x = G[i].x;
		p1.y = G[i].y;
		
		for (j = 0; j < i; j++)
		{
			if (valid[j] == 0) continue;
			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;
			
			xm = (p1.x + p2.x) / 2.0;
			ym = (p1.y + p2.y) / 2.0;
			
			for (n = 1; n <= M && ok; n++)
			{
				aried = 0;
				apartine_latura = 0;
				
				for (k = 1; k < A[n].size() && ok; k++)
				{
					p3 = A[n][k-1];
					p4 = A[n][k];
					
					aried += arie (p3, p4, xm, ym);
					if (arie (p3, p4, xm, ym) == 0)
						apartine_latura = 1;
					
					ok &= nuseintersecteaza (p1, p2, p3, p4);
				}
				if (G[i].p != G[j].p && (int)(aried + 0.02) == ariepoly[n] && !apartine_latura)
					ok = 0;
			}
			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;
}