Submission #3830687
Source Code Expand
#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 atan2l(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 sqrtl((A-B).sqrlen());}
struct dieGerade
{
derPunkt O,A;
dieGerade(){}
dieGerade(derPunkt O,derPunkt A):O(O),A(A){}
inline double theta(){return atan2l(A.y,A.x);}
inline double len(){return sqrtl(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;
if(fls(d1,d2))//should be strict
{
d1=(O.O-A)*(B-A);
d2=(O.O-B)*(A-B);
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()
{
double a,b,c,x0,y0,r0,w,x1,y1,r1,t1,d1,x2,y2,r2,t2,d2,t3,r3,k;
w=::w[1];
r0=::a[1].r;
s=s-::a[1].O;
t=t-::a[1].O;
x0=s.x;
y0=s.y;
a=v*v-w*w;
double vx,vy;
vx=v*cosl((t-s).theta());
vy=v*sinl((t-s).theta());
b=2*(x0*vx+y0*vy-r0*w);
c=x0*x0+y0*y0-r0*r0;
double s1=(-b+sqrtl(b*b-4*a*c))/(2*a),s2=(-b-sqrtl(b*b-4*a*c))/(2*a);
if(fle(s1,0)&&fle(s1,0)||fle(dis(s,t)/v,s1)&&fle(dis(s,t)/v,s2))
return printf("%.10LF",dis(s,t)/v);
t1=sqrtl((s.sqrlen()-r0*r0)/(v*v-w*w));
r3=sqrtl(t.sqrlen());
k=sqrtl(v*v-w*w);
r1=r0+t1*w;
double gamma=acosl(w/v);
d1=s.theta()-asinl(sinl(gamma)*v*t1/sqrtl(s.sqrlen()));
x1=cosl(d1)*r1;
y1=sinl(d1)*r1;
assert(feq(x1*x1+y1*y1,r1*r1));
double d3=t.theta();
if(d3>d1)d3-=2*pi;
double l=0,r=min(pi,d1-d3),res=1e18;
if(fls(k/w*log(r3/r1),r));
else
{
for(;r-l>eps;)
{
double mid=(l+r)/2;
d2=d1-mid;
r2=cosl(d2-d3)*r3-sinl(d2-d3)*r3*w/k;
if(k/w*log(r2/r1)<mid)
l=mid;
else r=mid;
}
d2=d1-l;
r2=cosl(d2-d3)*r3-sinl(d2-d3)*r3*w/k;
t2=(r2-r0)/w;
x2=cosl(d2)*r2;
y2=sinl(d2)*r2;
t3=t2+dis(t,derPunkt(x2,y2))/v;
if(res>t3)res=t3;
}
d1=s.theta()+asinl(sinl(gamma)*v*t1/sqrt(s.sqrlen()));
x1=cosl(d1)*r1;
y1=sinl(d1)*r1;
d3=t.theta();
if(d3<d1)d3+=2*pi;
assert(feq(x1*x1+y1*y1,r1*r1));
l=0;
r=min(pi,d3-d1);
if(fls(k/w*log(r3/r1),r));
else
{
for(;r-l>eps;)
{
double mid=(l+r)/2;
d2=d1+mid;
r2=cosl(d3-d2)*r3-sinl(d3-d2)*r3*w/k;
if(k/w*log(r2/r1)<mid)
l=mid;
else r=mid;
}
d2=d1+l;
r2=cosl(d3-d2)*r3-sinl(d3-d2)*r3*w/k;
t2=(r2-r0)/w;
x2=cosl(d2)*r2;
y2=sinl(d2)*r2;
t3=t2+dis(t,derPunkt(x2,y2))/v;
if(res>t3)res=t3;
}
if(res>1e17)puts("Impossible");
else printf("%.10LF",res);
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]);
}
return dis[t];
}
}G;
void AE(int a,int b,double c)
{
G.ins(a,b,c);
G.ins(b,a,c);
}
void seg(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());
}
bool 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);
};
bool arc(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;
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;
}
double dk(double alpha,double beta,double r)
{
if(alpha<=beta)return (beta-alpha)*r;
else return (beta-alpha+2*pi)*r;
}
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+cosl(alpha)*A.r,A.O.y+sinl(alpha)*A.r);
p[++cp]=derPunkt(B.O.x+cosl(alpha)*B.r,B.O.y+sinl(alpha)*B.r);
p[++cp]=derPunkt(A.O.x+cosl(beta)*A.r,A.O.y+sinl(beta)*A.r);
p[++cp]=derPunkt(B.O.x+cosl(beta)*B.r,B.O.y+sinl(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+cosl(alpha)*A.r,A.O.y+sinl(alpha)*A.r);
p[++cp]=derPunkt(B.O.x-cosl(alpha)*B.r,B.O.y-sinl(alpha)*B.r);
p[++cp]=derPunkt(A.O.x+cosl(beta)*A.r,A.O.y+sinl(beta)*A.r);
p[++cp]=derPunkt(B.O.x-cosl(beta)*B.r,B.O.y-sinl(beta)*B.r);
}
for(int i=0;i<cp;i+=2)
seg(i+1,i+2);
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])
{
derPunkt A=p[i],B=p[j],O=a[k].O;
double alpha=(A-O).theta(),beta=(B-O).theta();
if(arc(A,B,O,a[k].r,alpha,beta))
AE(i,j,dk(alpha,beta,a[k].r));
if(arc(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&&w[1]>0)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 |
8028 Byte |
Status |
WA |
Exec Time |
66 ms |
Memory |
4608 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
50 / 50 |
100 / 100 |
100 / 100 |
0 / 150 |
Status |
|
|
|
|
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 |
3 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 |
3 ms |
3712 KB |
11_rand18.txt |
AC |
3 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 |
3 ms |
3712 KB |
11_rand23.txt |
AC |
3 ms |
3712 KB |
11_rand24.txt |
AC |
3 ms |
3712 KB |
21_rand00.txt |
AC |
3 ms |
3712 KB |
21_rand01.txt |
AC |
4 ms |
3840 KB |
21_rand02.txt |
AC |
6 ms |
3840 KB |
21_rand03.txt |
AC |
66 ms |
4608 KB |
21_rand04.txt |
AC |
3 ms |
3712 KB |
21_rand05.txt |
AC |
22 ms |
4224 KB |
21_rand06.txt |
AC |
3 ms |
3712 KB |
21_rand07.txt |
AC |
4 ms |
3840 KB |
21_rand08.txt |
AC |
10 ms |
3968 KB |
21_rand09.txt |
AC |
10 ms |
3968 KB |
21_rand10.txt |
AC |
3 ms |
3712 KB |
21_rand11.txt |
AC |
10 ms |
3968 KB |
21_rand12.txt |
AC |
62 ms |
4608 KB |
21_rand13.txt |
AC |
3 ms |
3712 KB |
21_rand14.txt |
AC |
3 ms |
3712 KB |
21_rand15.txt |
AC |
16 ms |
4224 KB |
21_rand16.txt |
AC |
7 ms |
3840 KB |
21_rand17.txt |
AC |
3 ms |
3712 KB |
21_rand18.txt |
AC |
4 ms |
3840 KB |
21_rand19.txt |
AC |
47 ms |
4224 KB |
21_rand20.txt |
AC |
4 ms |
3840 KB |
21_rand21.txt |
AC |
6 ms |
3840 KB |
21_rand22.txt |
AC |
8 ms |
3968 KB |
21_rand23.txt |
AC |
10 ms |
3840 KB |
21_rand24.txt |
AC |
3 ms |
3712 KB |
31_rand00.txt |
AC |
58 ms |
4224 KB |
31_rand01.txt |
AC |
29 ms |
3968 KB |
31_rand02.txt |
AC |
40 ms |
4608 KB |
31_rand03.txt |
AC |
39 ms |
4224 KB |
31_rand04.txt |
AC |
34 ms |
4224 KB |
31_rand05.txt |
AC |
39 ms |
4224 KB |
31_rand06.txt |
AC |
25 ms |
4224 KB |
31_rand07.txt |
AC |
34 ms |
4224 KB |
31_rand08.txt |
AC |
31 ms |
4224 KB |
31_rand09.txt |
AC |
39 ms |
4352 KB |
31_rand10.txt |
AC |
62 ms |
4352 KB |
31_rand11.txt |
AC |
32 ms |
4224 KB |
31_rand12.txt |
AC |
36 ms |
4352 KB |
31_rand13.txt |
AC |
39 ms |
4608 KB |
31_rand14.txt |
AC |
36 ms |
4224 KB |
31_rand15.txt |
AC |
29 ms |
4224 KB |
31_rand16.txt |
AC |
31 ms |
4224 KB |
31_rand17.txt |
AC |
36 ms |
4224 KB |
31_rand18.txt |
AC |
26 ms |
4224 KB |
31_rand19.txt |
AC |
34 ms |
4224 KB |
31_rand20.txt |
AC |
6 ms |
3840 KB |
31_rand21.txt |
AC |
20 ms |
4608 KB |
31_rand22.txt |
AC |
11 ms |
3968 KB |
31_rand23.txt |
AC |
51 ms |
4608 KB |
31_rand24.txt |
AC |
3 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 |
WA |
3 ms |
3712 KB |
41_rand09.txt |
AC |
3 ms |
3712 KB |
41_rand10.txt |
WA |
3 ms |
3712 KB |
41_rand11.txt |
WA |
3 ms |
3712 KB |
41_rand12.txt |
AC |
3 ms |
3712 KB |
41_rand13.txt |
WA |
3 ms |
3712 KB |
41_rand14.txt |
AC |
3 ms |
3712 KB |
41_rand15.txt |
AC |
3 ms |
3712 KB |
41_rand16.txt |
AC |
3 ms |
3712 KB |
41_rand17.txt |
AC |
3 ms |
3712 KB |
41_rand18.txt |
AC |
3 ms |
3712 KB |
41_rand19.txt |
AC |
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 |
AC |
3 ms |
3712 KB |