Cod sursa(job #987641)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 21 august 2013 10:49:19
Problema Robot Scor 25
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.22 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

#define NMAX 3001
#define MMAX 26
#define eps 0.000001
#define pb push_back
#define mp make_pair
#define Punct pair < int , int >
#define Punctd pair < double , double >
#define sz(a) ((a).size())
#define INF 1<<30

vector <Punct> robot,st;
vector <Punct> obstacol[MMAX];
Punct H;
Punctd P;
int viz[NMAX],m;
double c[NMAX][NMAX],d[NMAX];

inline int cross_product(Punct A, Punct B, Punct C)
{
	return (B.first-A.first)*(C.second-A.second)-(C.first-A.first)*(B.second-A.second);
}

inline double dist(Punct A, Punct B)
{
	return (double)sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}

inline int egal(Punctd A, Punct B)
{
	if(fabs(A.first-B.first)<=eps && fabs(A.second-B.second)<=eps)
		return 1;
	return 0;
}

struct cmp {
	bool operator () (const Punct &A, const Punct &B) {
		return cross_product(H,A,B)>0;
	}
};

void Graham_scan(vector <Punct> &v)
{
	int i,lim,nr;
	sort(v.begin(),v.end());
	vector <Punct> :: iterator it=unique(v.begin(),v.end());
	v.resize(distance(v.begin(),it));
	lim=sz(v);
	H=*(v.begin());
	sort(v.begin(),v.end(),cmp());
	st.clear();
	st.pb(v[0]);
	st.pb(v[1]);
	nr=1;
	for(i=2;i<=lim-1;i++) {
		while(nr>=1 && cross_product(st[nr-1],st[nr],v[i])<=0) {
			nr--;
			st.pop_back();
		}
		nr++;
		st.pb(v[i]);
	}
	st.pb(st[0]);
	v=st;
}

void make_NFP(vector <Punct> &v)
{
	int i,lim;
	lim=sz(v);
	for(i=0;i<=lim-1;i++)
		for(vector <Punct> :: iterator it=robot.begin();it!=robot.end();it++)
			v.pb(mp(robot[0].first+v[i].first-(it->first),robot[0].second+v[i].second-(it->second)));
	Graham_scan(v);
}

void make_finish(int &x, int &y)
{
	int miny,i,n;
	miny=INF;
	n=sz(robot)-1;
	for(i=0;i<=n;i++)
		if(robot[i].second<miny)
			miny=robot[i].second;
	y=y+robot[0].second-miny;
}

inline int interior(Punct A, Punct B, Punct C)
{
	if(cross_product(A,B,C)!=0)
		return 0;
	if(min(B.first,C.first)<=A.first && A.first<=max(B.first,C.first) && min(B.second,C.second)<=A.second && A.second<=max(B.second,C.second))
		return 1;
	return 0;
}

inline int contur(Punct A, vector <Punct> v)
{
	int i,lim;
	lim=sz(v)-1;
	for(i=0;i<=lim-1;i++)
		if(interior(A,v[i],v[i+1]))
			return 1;
	return 0;
}

inline int intersecteaza(Punct A, Punct B, Punct C, Punct D)
{
	int a,b,c,a2,b2,c2,det;
	a=B.second-A.second;
	b=A.first-B.first;
	c=A.second*B.first-A.first*B.second;
	a2=D.second-C.second;
	b2=C.first-D.first;
	c2=C.second*D.first-C.first*D.second;
	
	det=a*b2-b*a2;
	if(det==0)
		return 0;
	P=mp((double)(b*c2-c*b2)/det,(double)(a2*c-a*c2)/det);
	return (cross_product(A,B,C)*cross_product(A,B,D)<=0 && cross_product(C,D,A)*cross_product(C,D,B)<=0);
}

inline int interior_poligon(Punct A, vector <Punct> v)
{
	int nr,i,lim,capete;
	Punct B,C;
	B.first=A.first;
	B.second=A.second;
	C.first=(5000);
	C.second=A.second;
	nr=0;
	capete=0;
	lim=sz(v)-1;
	for(i=0;i<=lim-1;i++) 
		if(intersecteaza(B,C,v[i],v[i+1])) {
			nr++;
			if(v[i].second==A.second)
				capete++;
		}
	if(intersecteaza(B,C,v[lim-1],v[lim])) {
		if(v[lim].second==A.second)
			capete++;
	}
	if(nr-capete/2<=0)
		return 0;
	return ((nr-capete/2)%2);
}

inline int visible(Punct A, Punct B, vector <Punct> v)
{
	int i,lim,c1,c2;
	lim=sz(v)-1;
	for(i=0;i<=lim-1;i++)
		if(cross_product(v[i],v[i+1],A)==0 && cross_product(v[i],v[i+1],B)==0)
			return 1;
	c1=contur(A,v);
	c2=contur(B,v);
	if(c1 && c2)
		return 0;
	if(interior_poligon(A,v) && c1==0) 
		return 0;
	if(interior_poligon(B,v) && c2==0)
		return 0;
	vector <Punctd> aux;
	for(i=0;i<=lim-1;i++)
		if(intersecteaza(A,B,v[i],v[i+1])) {
			if(egal(P,A) || egal(P,B))
				continue;
			aux.pb(P);
		}
	sort(aux.begin(),aux.end());
	vector <Punctd> :: iterator it=unique(aux.begin(),aux.end());
	aux.resize(it-aux.begin());
	return sz(aux)<=0;
}

double distanta(Punct A, Punct B)
{
	int i;
	if(A==B)
		return 0;
	for(i=1;i<=m;i++)
		if(visible(A,B,obstacol[i])==0)
			return INF;
	return dist(A,B);
}

double dijkstra(int n)
{
	int i,nod;
	double minim;
	for(i=1;i<=n;i++)
		d[i]=INF;
	while(viz[n]==0) {
		minim=INF;
		for(i=0;i<=n;i++)
			if(viz[i]==0 && d[i]<minim) {
				minim=d[i];
				nod=i;
			}
		viz[nod]=1;
		for(i=0;i<=n;i++)
			if(d[nod]+c[nod][i]<d[i])
				d[i]=d[nod]+c[nod][i];
	}
	return d[n];
}

int main ()
{
	int n,i,j,x,y,p,lim;
	double sol;
	ifstream f("robot.in");
	ofstream g("robot.out");
	f>>n;
	for(i=1;i<=n;i++) {
		f>>x>>y;
		robot.pb(mp(x,y));
	}
	f>>m;
	for(i=1;i<=m;i++) {
		f>>p;
		for(j=1;j<=p;j++) {
			f>>x>>y;
			obstacol[i].pb(mp(x,y));
		}
	}
	f>>x>>y;
	f.close();
	sort(robot.begin(),robot.end());
	for(i=1;i<=m;i++)
		make_NFP(obstacol[i]);
	vector <Punct> v;
	v.pb(robot[0]);
	for(i=1;i<=m;i++) {
		lim=sz(obstacol[i])-1;
		for(j=0;j<=lim-1;j++)
			v.pb(obstacol[i][j]);
	}
	v.pb(mp(x,y));
	lim=sz(v)-1;
	for(i=0;i<=lim;i++)
		for(j=0;j<=lim;j++) {
			if(i==j)
				continue;
			c[i][j]=distanta(v[i],v[j]);
		}
	sol=dijkstra(lim);
	if(sol==INF)
		g<<"-1";
	else {
		g<<fixed;
		g<<setprecision(2)<<sol;
	}
	g.close();
	return 0;
}