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 |
|
|
|
|
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 |