Cod sursa(job #945974)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 3 mai 2013 15:30:23
Problema Robot Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.6 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cmath>

#define maxinit 11
#define maxm 31
#define maxdim 2505
#define inf (1<<20)
#define inf_LL (1LL<<60)

using namespace std;

FILE*f=fopen("robot.in","r");
FILE*g=fopen("robot.out","w");

int vf_poligon,m,xs = inf,ys = inf,xd,yd,noduri;
int st[maxdim],used[maxdim*maxinit],inside[maxdim*maxinit],where[maxdim*maxinit];
double D[maxdim*maxinit];

struct point{
	point( int x = 0 , int y = 0 ):x(x),y(y){}
	int x,y;
	
	friend bool operator < ( const point &a , const point &b ){
		if ( a.x < b.x )	return 1;
		if ( a.x == b.x && a.y < b.y )	return 1;
		return 0;
	}
	friend bool operator <= ( const point &a , const point &b ){
		if ( a.x < b.x )	return 1;
		if ( a.x == b.x && a.y <= b.y )	return 1;
		return 0;
	}
};
vector<point>poligon,P[maxm];
point N[maxdim];
vector< pair<int,double> >G[maxdim*maxinit];

struct cmp{
	inline bool operator () ( const point &a , const point &b ){
		if ( a.x != b.x )	return a.x < b.x;
		return a.y < b.y;
	}
};

inline void citire () {
	
	fscanf(f,"%d",&vf_poligon);
	int x,y;
	for ( int i = 1 ; i <= vf_poligon ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		poligon.push_back(point(x,y));
		if ( x < xs )	xs = x;
		if ( y < ys )	ys = y;
	}
	
	fscanf(f,"%d",&m);
	for ( int i = 1 ; i <= m ; ++i ){
		int varfuri;
		fscanf(f,"%d",&varfuri);
		for ( int j = 1 ; j <= varfuri ; ++j ){
			fscanf(f,"%d %d",&x,&y);
			P[i].push_back(point(x,y));
		}
	}
	
	fscanf(f,"%d %d",&xd,&yd);
}

inline int det ( const point &a , const point &b , const point &c ){
	
	int d = (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
	return d;
}

inline void unic ( vector<point>&A ){
	
	vector<point>r;
	r.push_back(A[0]);
	for ( int i = 1 ; i < A.size() ; ++i ){
		if ( A[i].x != A[i-1].x || A[i].y != A[i-1].y ){
			r.push_back(A[i]);
		}
	}
	A = r;
}

vector<point> convex_hull ( vector<point>A ){
	
	sort(A.begin(),A.end(),cmp());
	unic(A);
	int n = A.size()-1;
	
	int vf = 0;
	st[++vf] = 0,st[++vf] = 1; used[1] = 1;
	for ( int i = 2 , pas = 1 ; i >= 0 ; i += ( pas = (i == n ? -pas : pas)) ){
		if ( used[i] )	continue ;
		
		while ( vf >= 2 && det(A[st[vf-1]],A[st[vf]],A[i]) < 0 ){
			used[st[vf--]] = 0;
		}
		st[++vf] = i; used[i] = 1;
	}
	
	vector<point>r;
	for ( int i = 1 ; i < vf ; ++i ){
		r.push_back(A[st[i]]);
	}
	
	for ( int i = 0 ; i <= n ; ++i )	used[i] = st[i] = 0;
	
	return r;
}

inline void nofitpolygon ( vector<point>&poligon , vector<point>&origine ){
	
	vector<point>A;
	for ( int i = 0 ; i < poligon.size() ; ++i ){
		for ( int j = 0 ; j < origine.size() ; ++j ){
			
			int newx = poligon[i].x + xs - origine[j].x;
			int newy = poligon[i].y + ys - origine[j].y;
			A.push_back(point(newx,newy));
		}
	}
	
	poligon = convex_hull(A);
}

inline void new_polygons () {
	
	for ( int i = 1 ; i <= m ; ++i ){
		nofitpolygon(P[i],poligon);
	}
}

inline void check_insides () {
	
	for ( int i = 1 ; i <= noduri ; ++i ){
		
		for ( int p = 1 ; p <= m ; ++p ){
			
			int in = 1;
			for ( int j = 0 ; j < (int)P[p].size()-1 ; ++j ){
				if ( det(P[p][j],P[p][j+1],N[i]) <= 0 ){
					in = 0;
					break ;
				}
			}
			
			if ( in ){
				inside[i] = 1;
				break ;
			}
		}
	}
}

inline double dist ( const point &a , const point &b ){
	
	double distanta = (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y);
	return sqrt(distanta);
}

inline int semn ( const int &x ){
	if ( x < 0 )	return -1;
	if ( x > 0 )	return 1;
	return 0;
}

inline bool intersection ( const point &A , const point &B , const point &C , const point &D ){
	
	int d1,d2;
	
	d1 = semn(det(A,B,C));
	d2 = semn(det(A,B,D));
	if ( d1 * d2 >= 0 ) 	return 0;
	
	d1 = semn(det(C,D,A));
	d2 = semn(det(C,D,B));
	if ( d1 * d2 >= 0 )		return 0;
	
	return 1;
}

inline void build_graph () {
	
	noduri = 1; N[1] = point(xs,ys);
	for ( int i = 1 ; i <= m ; ++i ){
		P[i].push_back(P[i][0]);
		for ( int j = 0 ; j < (int)P[i].size()-1 ; ++j ){
			++noduri;
			N[noduri] = P[i][j];
		}
	}
	++noduri; N[noduri] = point(xd,yd);
	
	check_insides();
	
	for ( int i = 1 ; i <= noduri ; ++i ){
		if ( inside[i] )	continue ;
		
		for ( int j = i+1 ; j <= noduri ; ++j ){
			if ( inside[j] )	continue ;
			
			int ok = 1;
			for ( int p = 1 ; p <= m && ok ; ++p ){
				
				int col = 0,lastcol = -1;
				for ( int x = 0 ; x < (int)P[p].size() && ok ; ++x ){
					point varf = P[p][x];
					if ( !det(N[i],N[j],varf) && min(N[i],N[j]) <= varf && varf <= max(N[i],N[j])  ){
						++col;
						if ( lastcol != -1 ){
							if ( col == 2 && lastcol != x-1 && !(x == (int)P[p].size()-1 && lastcol == 0) )	ok = 0;
						}
						lastcol = x;
					}
				}
				
				for ( int x = 0 ; x < (int)P[p].size()-1 && ok ; ++x ){
					if ( intersection(N[i],N[j],P[p][x],P[p][x+1]) ){
						ok = 0;
					}
				}
			}
			
			if ( (N[i].x == N[j].x && N[i].y == N[j].y) || ok ){
				double distanta = dist(N[i],N[j]);
				G[i].push_back(make_pair(j,distanta));
				G[j].push_back(make_pair(i,distanta));
			}
		}
	}
}

inline void dijkstra () {
	
	for ( int i = 0 ; i <= noduri ; ++i ){
		D[i] = inf_LL;
	}
	D[1] = 0;
	
	for ( int pas = 1 ; pas <= noduri ; ++pas ){
		
		int nod = 0;
		for ( int i = 1 ; i <= noduri ; ++i ){
			if ( used[i] )	continue ;
			if ( D[i] < D[nod] ){
				nod = i;
			}
		}
		
		if ( nod == noduri || D[nod] == inf_LL )	break ;
		
		used[nod] = 1;
		for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int vecin = itt->first; double cost = itt->second;
			if ( D[vecin] > D[nod]+cost ){
				D[vecin] = D[nod]+cost;
			}
		}
	}
	
	if ( D[noduri] != inf_LL ){
		fprintf(g,"%.5lf\n",D[noduri]);
	}
	else{
		fprintf(g,"-1\n");
	}
}

int main () {
	
	citire();
	
	new_polygons();
	
	build_graph();
	dijkstra();
	
	fclose(f);
	fclose(g);
	
	return 0;
}