Cod sursa(job #335631)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 30 iulie 2009 18:36:06
Problema Robot Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.57 kb
/*
 * Author: Paul - Dan Baltescu, University of Bucharest
 */

#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cmath>

using namespace std;

const int MAXM = 30;
const int MAXP = 550;
const int INF = 1000000000;
const double eps = 0.00000001;

#define getSemiplane(p) (p.x > 0 || (p.x == 0 && p.y > 0))
#define ff first
#define ss second

struct Point
{
	double x, y;

	Point() :x(0), y(0) {}
	Point(double a, double b) : x(a), y(b) {}

	Point operator-(Point p) const
	{
		return Point(x - p.x, y - p.y);
	}

	Point operator+(Point p) const
	{
		return Point(x + p.x, y + p.y);
	}

	int operator==(Point p) const
	{
		return x == p.x && y == p.y;
	}

	friend istream& operator>>(istream &fin, Point &p)
	{
		fin >> p.x >> p.y;
		return fin;
	}

	friend ostream& operator<<(ostream &fout, Point p)
	{
		fout << "(" << p.x << "," << p.y << ")";
		return fout;
	}
};

int M, N;
double Sol;
vector <Point> robot, puncte;
vector <Point> obst[MAXM];
Point start, finish;
int Area[MAXM];
vector < pair <int, double> > A[MAXP];
int U[MAXP];
double Cost[MAXP];

void readData()
{
	ifstream fin("robot.in");
	int N;

	fin >> N;

	for (int i = 0; i < N; ++i)
	{
		Point p;
		fin >> p;
		robot.push_back(p);
	}

	fin >> M;

	for (int i = 0; i < M; ++i)
	{
		int nr;

		fin >> nr;

		for (int j = 0; j < nr; ++j) 
		{
			Point p;
			fin >> p;
			obst[i].push_back(p);
		}
	}

	start = robot[0];
	for (int i = 1; i < (int) robot.size(); ++i)
	{
		if (robot[i].x < start.x) start.x = robot[i].x;
		if (robot[i].y < start.y) start.y = robot[i].y;
	}

	fin >> finish;
}

int cmp(Point p1, Point p2)
{
	int sp1 = getSemiplane(p1);
	int sp2 = getSemiplane(p2);

	return sp1 < sp2 || (sp1 == sp2 && p1.y*p2.x < p1.x*p2.y);
}

vector <Point> buildObstacle(const vector <Point>& polig1, const vector <Point>& polig2)
{
	vector <Point> vect, res;

	// creez un set de vectori matematici astfel:
	// laturile din robot parcurse in sens antitrigonometric
	// laturile din obstacol parcurse in sens trigonometric

	for (int i = 1; i < (int) polig1.size(); ++i) vect.push_back(polig1[i-1] - polig1[i]);
	vect.push_back(polig1[ polig1.size()-1 ] - polig1[0]);

	for (int i = 1; i < (int) polig2.size(); ++i) vect.push_back(polig2[i] - polig2[i-1]);
	vect.push_back(polig2[0] - polig2[ polig2.size()-1 ]);

	// sortez vectorii roata in jurul originii

	sort(vect.begin(), vect.end(), cmp);

	// stabilesc unde trebuie translatat obstacolul
	
	Point p1 = polig1[0], p2 = polig1[0], p3 = polig2[0];
	
	for (int i = 1; i < (int) polig1.size(); ++i)
	{
		if (polig1[i].y < p1.y) p1 = polig1[i];
		if (polig1[i].x < p2.x || (polig1[i].x == p2.x && polig1[i].y < p2.y)) p2 = polig1[i];
	}

	for (int i = 1; i < (int) polig2.size(); ++i) 
		if (polig2[i].x > p3.x || (polig2[i].x == p3.x && polig2[i].y > p3.y)) p3 = polig2[i];

	p3 = p3 - Point(0, p2.y - p1.y);

	// construiesc noul obstacol
	
	res.push_back(p3);
	for (int i = 0; i < (int) vect.size() - 1; ++i) res.push_back(res[i] + vect[i]);

	assert(res.size() == vect.size());
	assert(res[res.size() - 1] + vect[ vect.size() - 1] == p3);

	return res;
}

void calcAreas()
{
	for (int i = 0; i < M; ++i)
	{
		for (int j = 1; j < (int) obst[i].size(); ++j) Area[i] += obst[i][j-1].x * obst[i][j].y - obst[i][j].x * obst[i][j-1].y;
		Area[i] += obst[i][ obst[i].size()-1 ].x * obst[i][0].y - obst[i][0].x * obst[i][ obst[i].size()-1 ].y;
	}
}

inline double crossProduct(Point p1, Point p2, Point p3)
{
	return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}

inline int crossed(Point p1, Point p2, Point p3, Point p4)
{
	if ((p1 == p3 && p2 == p4) || (p1 == p4 && p2 == p3)) return 2;

	// intersectez bounding box-urile

	if (max(min(p1.x, p2.x), min(p3.x, p4.x)) > min(max(p1.x, p2.x), max(p3.x, p4.x))) return 0;
	if (max(min(p1.y, p2.y), min(p3.y, p4.y)) > min(max(p1.y, p2.y), max(p3.y, p4.y))) return 0;

	// intersectez segmentele

	int v1 = crossProduct(p1, p2, p3) * crossProduct(p1, p2, p4);
	int v2 = crossProduct(p3, p4, p1) * crossProduct(p3, p4, p2);

	if (v1 < 0 && v2 < 0) return 3;
	return (v1 == 0) || (v2 == 0);
}

inline double dist(Point p1, Point p2)
{
	return sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y));
}

inline int onTheLine(Point p, Point p1, Point p2)
{
	return fabs( dist(p, p1) + dist(p, p2) - dist(p1, p2)) < eps;
}

inline int insidePolygon(Point p, int x)
{
	double area = 0;

	for (int i = 1; i < (int) obst[x].size(); ++i)
	{
		area += abs( crossProduct(p, obst[x][i], obst[x][i-1]) );
		if (onTheLine(p, obst[x][i], obst[x][i-1])) return 0;
	}

	area += abs( crossProduct(p, obst[x][0], obst[x][ obst[x].size()-1 ]) );
	if (onTheLine(p, obst[x][0], obst[x][ obst[x].size()-1 ]) ) return 0;

	return fabs(area - Area[x]) < eps;
}

inline int goodSegment(Point p1, Point p2, int magic)
{
	for (int i = 0; i < M; ++i)
	{
		if (insidePolygon(p1, i) || insidePolygon(p2, i)) return 0;

		if (insidePolygon(Point((p1.x+p2.x)/2, (p1.y+p2.y)/2), i)) return 0;

		int aux = 0;

		for (int j = 1; j < (int) obst[i].size(); ++j)
		{
			aux = crossed(p1, p2, obst[i][j-1], obst[i][j]);
			if (aux == 3) return 0;
		}

		aux = crossed(p1, p2, obst[i][0], obst[i][ obst[i].size()-1 ]);
		if (aux == 3) return 0;
	}

	return 1;
}

void makeGraph()
{
	// Aleg punctele interesante
	
	puncte.push_back(start);
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < (int) obst[i].size(); ++j) puncte.push_back(obst[i][j]);
	puncte.push_back(finish);

	N = puncte.size();

	//for (int i = 0; i < N; ++i) cout << puncte[i] << endl;

	// Fac graful propriu-zis
	
	for (int i = 0; i < N; ++i)
		for (int j = i+1; j < N; ++j)
			if (goodSegment(puncte[i], puncte[j], (i != 0) + (j != N-1) ))
			{
				A[i].push_back( make_pair(j, dist(puncte[i], puncte[j])) );
				A[j].push_back( make_pair(i, dist(puncte[i], puncte[j])) );
			}

/*	for (int i = 0; i < N; ++i)
	{
		cout << i << ": ";
		for (int j = 0; j < (int) A[i].size(); ++j) cout << A[i][j].ff << " ";
		cout << endl;
	}*/
}

double doDijkstra()
{
	for (int i = 1; i < N; ++i) Cost[i] = INF;

	for (int i = 1; i < N && !U[N-1]; ++i)
	{
		int nod = 0;
		for (int j = 1; j < N; ++j) 
			if (!U[j] && (Cost[j] < Cost[nod] || U[nod])) nod = j;

		for (int j = 0; j < (int) A[nod].size(); ++j)
			if (Cost[nod] + A[nod][j].ss < Cost[A[nod][j].ff]) Cost[A[nod][j].ff] = Cost[nod] + A[nod][j].ss;

		U[nod] = 1;
	}

	if (Cost[N-1] == INF) return -1;
	return Cost[N-1];
}

void writeData()
{
	ofstream fout("robot.out");

	fout.precision(2);

	fout << fixed << Sol << endl;
}

int main()
{
	readData();

	for (int i = 0; i < M; ++i) obst[i] = buildObstacle(robot, obst[i]);
	calcAreas();

	makeGraph();
	Sol = doDijkstra();

	writeData();

	return 0;
}