Submission #3814749


Source Code Expand

#define DEBUG

#ifndef DEBUG
#define NDEBUG
#endif

#include<functional>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define double long double
const double eps=1e-12;
struct derPunkt
{
	double x,y;
	derPunkt():x(0),y(0){}
	derPunkt(double x,double y):x(x),y(y){}
	inline double theta(){return atan2(y,x);}
	inline double sqrlen(){return x*x+y*y;}
};
istream&operator>>(istream&ist,derPunkt&b)
{
	ist >> b.x >> b.y;
	return ist;
}
ostream&operator<<(ostream&ost,derPunkt&b)
{
	ost << '(' << b.x << ',' << b.y << ')';
	return ost;
}
inline derPunkt operator+(const derPunkt a,const derPunkt b){return derPunkt(a.x+b.x,a.y+b.y);}
inline derPunkt operator-(const derPunkt a,const derPunkt b){return derPunkt(a.x-b.x,a.y-b.y);}
inline double operator*(const derPunkt a,const derPunkt b){return a.x*b.x+a.y*b.y;}
inline double operator/(const derPunkt a,const derPunkt b){return a.x*b.y-b.x*a.y;}
inline bool fle(double a,double b){return a<b+eps;}//not strict
inline bool fls(double a,double b){return a+eps<b;}//strict
inline bool feq(double a,double b){return fabs(a-b)<eps;}
inline double dis(derPunkt A,derPunkt B){return sqrt((A-B).sqrlen());}
struct dieGerade
{
	derPunkt O,A;
	dieGerade(){}
	dieGerade(derPunkt O,derPunkt A):O(O),A(A){}
	inline double theta(){return atan2(A.y,A.x);}
	inline double len(){return sqrt(A.sqrlen());}
};
inline bool straight(const dieGerade a,const dieGerade b){return a.A*b.A==0;}
struct derKreis
{
	derPunkt O;
	double r;
	derKreis(){}
	derKreis(derPunkt O,double r):O(O),r(r){}
};
inline bool operator<(const derPunkt A,const derKreis B){return fls((A-B.O).sqrlen(),B.r*B.r);}//strict
inline bool operator==(const derPunkt A,const derKreis B){return feq((A-B.O).sqrlen(),B.r*B.r);}
inline bool operator*(derKreis O,dieGerade l)//return 1 => should be strict
{
	derPunkt A=l.O,B=l.O+l.A;
	if(A<O||B<O)return 1;//should be strict
	double a,b,c;//ax+by+c=0
	a=-l.A.y;
	b=l.A.x;
	c=A/B;
	double d1=a*O.O.x+b*O.O.y+c,d2=O.r*O.r*(a*a+b*b);
	d1=d1*d1;
	//cerr << a << ' ' << b << ' ' << c << ' ' << d1 << ' ' << d2 << endl;
	if(fls(d1,d2))//should be strict
	{
		d1=(O.O-A)*(B-A);
		d2=(O.O-B)*(A-B);
		//cerr << d1 << ' ' << d2 << endl;
		return fls(0,d1)&&fls(0,d2);//should be strict
	}
	else return 0;
}
int n;
derKreis a[13];
derPunkt s,t,p[111111];
int cp;
double w[13],v;
const double pi=acos(-1);
namespace uno
{
	int main()
	{
		return 0;
	}
}
namespace dos
{
	struct derGraf
	{
		int s,t,m;
		int n;
		vector<int>u,v;
		vector<double>w;
		void ins(int a,int b,double c)
		{
			u.push_back(a);
			v.push_back(b);
			w.push_back(c+eps);
			++m;
		}
		double dis[111111];
		inline void cmin(double&a,const double b){if(a>b)a=b;}
		double bf()
		{
			for(int i=1;i<=n;++i)dis[i]=1e18;
			dis[s]=0;
			for(int j=0;j<n;++j)
			{
				for(int i=0;i<m;++i)
					cmin(dis[v[i]],dis[u[i]]+w[i]);
				//for(int i=1;i<=n;++i)printf("%lf\n",dis[i]);
			}
			return dis[t];
		}
	}G;
	void AE(int a,int b,double c)
	{
		//if(c>0)cout << "AE " << a << ' ' << p[a] << ' ' << b << ' ' << p[b] << ' ' << c << endl;
		G.ins(a,b,c);
		G.ins(b,a,c);
	}
	int main()
	{
		n+=2;
		a[n]=derKreis(s,0);
		a[n-1]=derKreis(t,0);
		for(int i=1;i<=n;++i)
			for(int j=i+1;j<=n;++j)
			{
				derKreis A=a[i];
				derKreis B=a[j];
				if(A.r<B.r)swap(A,B);
				derKreis C(A.O,A.r-B.r);
				derPunkt D=B.O;
				dieGerade l(C.O,D-C.O);
				if(fle(l.len(),C.r))continue;
				double theta=acos(C.r/l.len());
				double alpha=l.theta()+theta,beta=l.theta()-theta;
				p[++cp]=derPunkt(A.O.x+cos(alpha)*A.r,A.O.y+sin(alpha)*A.r);
				p[++cp]=derPunkt(B.O.x+cos(alpha)*B.r,B.O.y+sin(alpha)*B.r);
				p[++cp]=derPunkt(A.O.x+cos(beta)*A.r,A.O.y+sin(beta)*A.r);
				p[++cp]=derPunkt(B.O.x+cos(beta)*B.r,B.O.y+sin(beta)*B.r);
			}
		for(int i=1;i<=n;++i)
			for(int j=i+1;j<=n;++j)
			{
				derKreis A=a[i];
				derKreis B=a[j];
				if(A.r<B.r)swap(A,B);
				derKreis C(A.O,A.r+B.r);
				derPunkt D=B.O;
				dieGerade l(C.O,D-C.O);
				if(fle(l.len(),C.r))continue;
				double theta=acos(C.r/l.len());
				double alpha=l.theta()+theta,beta=l.theta()-theta;
				p[++cp]=derPunkt(A.O.x+cos(alpha)*A.r,A.O.y+sin(alpha)*A.r);
				p[++cp]=derPunkt(B.O.x-cos(alpha)*B.r,B.O.y-sin(alpha)*B.r);
				p[++cp]=derPunkt(A.O.x+cos(beta)*A.r,A.O.y+sin(beta)*A.r);
				p[++cp]=derPunkt(B.O.x-cos(beta)*B.r,B.O.y-sin(beta)*B.r);
				//cout << i << ' ' << j << ' ' << p[cp-3] << p[cp-2] << p[cp-1] << p[cp] << endl;
			}
		//for(int i=1;i<=cp;++i)cout << i << p[i] << endl;
		//puts(a[2]*dieGerade(p[61],p[62])?"YES":"NO");
		auto straight=[](int alpha,int beta)
		{
			derPunkt A=p[alpha],B=p[beta];
			dieGerade l=dieGerade(A,B-A);
			for(int j=1;j<=n;++j)
				if(a[j]*l)
					return;
			AE(alpha,beta,l.len());
		};
		for(int i=0;i<cp;i+=2)
			straight(i+1,i+2);
		auto gay=[](derPunkt A,derPunkt B,derPunkt O,double r,const double&alpha,const double&beta)
		{
			for(int i=1;i<=n;++i)
			{
				if(A<a[i]||B<a[i])return false;
				auto dans=[](const double&a,const double&b,const double&c)
				{
					if(fls(a,b))return fls(a,c)&&fls(c,b);
					else return fls(c,b)||fls(a,c);
				};
				if(fls(fabs(a[i].r-r),dis(O,a[i].O))&&fls(dis(O,a[i].O),a[i].r+r))
				{
					double gamma=(a[i].O-O).theta();
					if(dans(alpha,beta,gamma))return false;
				}
			}
			return true;
		};
		for(int i=1;i<=cp;++i)
		{
			for(int j=i+1;j<=cp;++j)
			{
				for(int k=1;k<=n;++k)
				{
					if(p[i]==a[k]&&p[j]==a[k])
					{
						//cerr << "Point " << p[i] << " and " << p[j] << " are on circ centered at " << a[k].O << " with radius " << a[k].r << endl;
						derPunkt A=p[i],B=p[j],O=a[k].O;
						auto dk=[](double alpha,double beta,double r)
						{
							if(alpha<=beta)return (beta-alpha)*r;
							else return (beta-alpha+2*pi)*r;
						};
						double alpha=(A-O).theta(),beta=(B-O).theta();
						if(gay(A,B,O,a[k].r,alpha,beta))
							AE(i,j,dk(alpha,beta,a[k].r));
						if(gay(B,A,O,a[k].r,beta,alpha))
							AE(j,i,dk(beta,alpha,a[k].r));
					}
				}
			}
		}
		G.s=cp+1;
		G.t=cp+2;
		p[cp+1]=s;
		p[cp+2]=t;
		G.n=cp+2;
		for(int i=1;i<=cp;++i)
		{
			if(feq(dis(s,p[i]),0))AE(G.s,i,0);
			if(feq(dis(t,p[i]),0))AE(i,G.t,0);
		}
		double res=G.bf();
		if(res>1e17)return puts("Impossible");
		for(int i=1;i<=n;++i)
			if(t<derKreis(a[i].O,a[i].r+res/v*w[i]))return puts("Impossible");
		printf("%.10LF",G.bf()/v);
		return 0;
	}
	
}
int main()
{
	cin >> s >> t >> v >> n;
	for(int i=1;i<=n;++i)
		cin >> a[i].O >> a[i].r >> w[i];
	//if(n==1)uno::main();
	/*else */dos::main();
	return 0;
}

Submission Info

Submission Time
Task D - 魔女
User alphaGem
Language C++14 (GCC 5.4.1)
Score 250
Code Size 6847 Byte
Status WA
Exec Time 73 ms
Memory 4608 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 50 / 50 100 / 100 100 / 100 0 / 150
Status
AC × 25
AC × 50
AC × 75
AC × 19
WA × 6
Set Name Test Cases
Subtask1 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt
Subtask2 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt
Subtask3 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt
Subtask4 41_rand00.txt, 41_rand01.txt, 41_rand02.txt, 41_rand03.txt, 41_rand04.txt, 41_rand05.txt, 41_rand06.txt, 41_rand07.txt, 41_rand08.txt, 41_rand09.txt, 41_rand10.txt, 41_rand11.txt, 41_rand12.txt, 41_rand13.txt, 41_rand14.txt, 41_rand15.txt, 41_rand16.txt, 41_rand17.txt, 41_rand18.txt, 41_rand19.txt, 41_rand20.txt, 41_rand21.txt, 41_rand22.txt, 41_rand23.txt, 41_rand24.txt
Case Name Status Exec Time Memory
11_rand00.txt AC 4 ms 3712 KB
11_rand01.txt AC 3 ms 3712 KB
11_rand02.txt AC 3 ms 3712 KB
11_rand03.txt AC 3 ms 3712 KB
11_rand04.txt AC 3 ms 3712 KB
11_rand05.txt AC 3 ms 3712 KB
11_rand06.txt AC 3 ms 3712 KB
11_rand07.txt AC 3 ms 3712 KB
11_rand08.txt AC 3 ms 3712 KB
11_rand09.txt AC 3 ms 3712 KB
11_rand10.txt AC 3 ms 3712 KB
11_rand11.txt AC 3 ms 3712 KB
11_rand12.txt AC 3 ms 3712 KB
11_rand13.txt AC 3 ms 3712 KB
11_rand14.txt AC 3 ms 3712 KB
11_rand15.txt AC 3 ms 3712 KB
11_rand16.txt AC 3 ms 3712 KB
11_rand17.txt AC 4 ms 3712 KB
11_rand18.txt AC 4 ms 3712 KB
11_rand19.txt AC 3 ms 3712 KB
11_rand20.txt AC 3 ms 3712 KB
11_rand21.txt AC 3 ms 3712 KB
11_rand22.txt AC 4 ms 3712 KB
11_rand23.txt AC 3 ms 3712 KB
11_rand24.txt AC 4 ms 3712 KB
21_rand00.txt AC 4 ms 3712 KB
21_rand01.txt AC 4 ms 3840 KB
21_rand02.txt AC 6 ms 3840 KB
21_rand03.txt AC 73 ms 4608 KB
21_rand04.txt AC 3 ms 3712 KB
21_rand05.txt AC 24 ms 4224 KB
21_rand06.txt AC 3 ms 3712 KB
21_rand07.txt AC 4 ms 3840 KB
21_rand08.txt AC 11 ms 3968 KB
21_rand09.txt AC 11 ms 3968 KB
21_rand10.txt AC 3 ms 3712 KB
21_rand11.txt AC 11 ms 3968 KB
21_rand12.txt AC 69 ms 4608 KB
21_rand13.txt AC 6 ms 3840 KB
21_rand14.txt AC 3 ms 3712 KB
21_rand15.txt AC 17 ms 4224 KB
21_rand16.txt AC 7 ms 3840 KB
21_rand17.txt AC 3 ms 3712 KB
21_rand18.txt AC 5 ms 3840 KB
21_rand19.txt AC 51 ms 4224 KB
21_rand20.txt AC 5 ms 3840 KB
21_rand21.txt AC 7 ms 3840 KB
21_rand22.txt AC 9 ms 3968 KB
21_rand23.txt AC 10 ms 3840 KB
21_rand24.txt AC 4 ms 3712 KB
31_rand00.txt AC 63 ms 4224 KB
31_rand01.txt AC 32 ms 3968 KB
31_rand02.txt AC 45 ms 4608 KB
31_rand03.txt AC 43 ms 4224 KB
31_rand04.txt AC 38 ms 4224 KB
31_rand05.txt AC 42 ms 4224 KB
31_rand06.txt AC 27 ms 4224 KB
31_rand07.txt AC 37 ms 4224 KB
31_rand08.txt AC 34 ms 4224 KB
31_rand09.txt AC 43 ms 4352 KB
31_rand10.txt AC 67 ms 4352 KB
31_rand11.txt AC 38 ms 4224 KB
31_rand12.txt AC 40 ms 4352 KB
31_rand13.txt AC 43 ms 4608 KB
31_rand14.txt AC 39 ms 4224 KB
31_rand15.txt AC 32 ms 4224 KB
31_rand16.txt AC 34 ms 4224 KB
31_rand17.txt AC 40 ms 4224 KB
31_rand18.txt AC 29 ms 4224 KB
31_rand19.txt AC 37 ms 4224 KB
31_rand20.txt AC 7 ms 3840 KB
31_rand21.txt AC 22 ms 4608 KB
31_rand22.txt AC 12 ms 3968 KB
31_rand23.txt AC 56 ms 4608 KB
31_rand24.txt AC 4 ms 3712 KB
41_rand00.txt AC 3 ms 3712 KB
41_rand01.txt AC 3 ms 3712 KB
41_rand02.txt AC 3 ms 3712 KB
41_rand03.txt AC 3 ms 3712 KB
41_rand04.txt AC 3 ms 3712 KB
41_rand05.txt AC 3 ms 3712 KB
41_rand06.txt AC 3 ms 3712 KB
41_rand07.txt AC 3 ms 3712 KB
41_rand08.txt AC 3 ms 3712 KB
41_rand09.txt AC 3 ms 3712 KB
41_rand10.txt AC 3 ms 3712 KB
41_rand11.txt AC 3 ms 3712 KB
41_rand12.txt AC 3 ms 3712 KB
41_rand13.txt AC 3 ms 3712 KB
41_rand14.txt AC 3 ms 3712 KB
41_rand15.txt WA 3 ms 3712 KB
41_rand16.txt WA 3 ms 3712 KB
41_rand17.txt WA 3 ms 3712 KB
41_rand18.txt WA 3 ms 3712 KB
41_rand19.txt WA 3 ms 3712 KB
41_rand20.txt AC 3 ms 3712 KB
41_rand21.txt AC 3 ms 3712 KB
41_rand22.txt AC 3 ms 3712 KB
41_rand23.txt AC 3 ms 3712 KB
41_rand24.txt WA 3 ms 3712 KB