QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33333 | #3008. Rocket Powered Hovercraft | simonfallon19 | AC ✓ | 3ms | 4340kb | C++17 | 8.3kb | 2022-05-31 13:43:29 | 2022-05-31 13:43:30 |
Judging History
answer
//#pragma GCC optimize("O3")
////(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
//#pragma comment(linker, "/stack:200000000")
////(UNCOMMENT WHEN NEEDED)
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define fi first
#define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el
#define sz(v) ((int)v.size())
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef vector<int> vi;
typedef vector<ll> vll;
const double pi = acos(-1), eps = 1e-9;
const int inf = 1e9, mod = 1e9+7, N = 1e5 + 10;
int x, y;
double v, w, r, a, nor;
struct pt { // for 3D add z coordinate
double x,y;
pt(double x, double y):x(x),y(y){}
pt(){}
double norm2(){return abs((*this)*(*this));}
double norm(){return sqrt(norm2());}
bool operator==(pt p){return abs(x-p.x)<=eps&&abs(y-p.y)<=eps;}
bool operator!=(pt p){ return !operator==(p);}
bool operator<(pt p)const{ // for convex hull/set/map
return x<p.x-eps||(abs(x-p.x)<=eps&&y<p.y-eps);}
pt operator+(pt p){return pt(x+p.x,y+p.y);}
pt operator-(pt p){return pt(x-p.x,y-p.y);}
pt operator*(double t){return pt(x*t,y*t);}
pt operator/(double t){return pt(x/t,y/t);}
///DOT
double operator*(pt p){return x*p.x+y*p.y;}
// pt operator%(pt p){ // 3D
// return pt(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);}
double angle(pt p){ ///[0, pi]
double co = *this*p/(norm()*p.norm());
return acos(max(-1.0, min(1.0, co)));
}
pt unit(){return *this/norm();}
double operator%(pt p){return x*p.y-y*p.x;}
/// 2D from now on
bool left(pt p, pt q){ // is it to the left of directed line pq?
return (q-p)%(*this-p)>eps;
}
int left_int(pt p, pt q){ // is it to the left of directed line pq?
double cro = (q-p)%(*this-p);
if(cro < eps)
return -1;
else
return (abs(cro) <= eps ? 0 : 1);
}
pt rot(pt r){return pt(*this%r,*this*r);}
pt rot(double a){return rot(pt(sin(a),cos(a)));}
pt rotp(double a, pt p){
pt aux = (*this - p).rot(a);
return aux + p;
}
};
pt ccw90(1,0), cw90(-1,0);
int sgn(double x){
if(x<0)
return -1;
else if(abs(x) <= eps)
return 0;
else
return 1;
}
int sgn2(double x){return x<0?-1:1;}
struct ln {
pt p, pq; //POINT + DIRECTION
ln(pt p, pt q) : p(p), pq(q-p){}
ln(double a, double b, double c) : p(b == 0 ? pt(-c/a, 0) : pt(0, -c/b)), pq(pt(b, -a)){} ///ax + by + c = 0
ln(){}
bool has(pt r){return dist(r)<=eps;} ///check if point belongs
bool seghas(pt r){return has(r)&&(r-p)*(r-(p+pq))<=eps;} ///check if point belongs to segment PQ
// bool operator /(ln l){return (pq.unit()^l.pq.unit()).norm()<=eps;} // 3D
bool operator/(ln l){return abs(pq.unit()%l.pq.unit())<=eps;} /// PARALLEL CHECK
bool operator==(ln l){return *this/l&&has(l.p);}
pt operator^(ln l){ /// intersection ln-ln
if(*this/l) return pt(inf,inf);
pt r=l.p+l.pq*((p-l.p)%pq/(l.pq%pq));
// if(!has(r)){return pt(NAN,NAN,NAN);} // check only for 3D
return r;
}
double angle(ln l){return pq.angle(l.pq);} ///angle bet. 2 lines
int side(pt r){return has(r)?0:sgn2(pq%(r-p));} /// 1=L, 0= on, -1=R
pt proj(pt r){return p+pq*((r-p)*pq/pq.norm2());}
pt refl(pt r){return proj(r)*2-r;}
double dist(pt r){return (r-proj(r)).norm();}
double dist2(pt r){return (r - proj(r)).norm2();}
// ls dist(ln l){ // only 3D
// if(*this/l)return dist(l.p);
// return abs((l.p-p)*(pq^l.pq))/(pq^l.pq).norm();
// }
ln rot(pt a){return ln(p,p+pq.rot(a));} /// 2D respecto a P
ln rot(double a){return ln(p,p+pq.rot(a));} /// 2D respecto a P
ln perp_at(pt r){return ln(r, r+pq.rot(ccw90));}
bool cmp_proj(pt r, pt s){return pq*r<pq*s;}
int cmp_int(pt r, pt s){
if(pq*r < pq*s)
return -1;
else
return (pq*r == pq*s ? 0 : 1);
}
ln trans(pt d){ return ln(p + d, pq);} ///d = dir. vec
};
ln bisec(ln l, ln m){ /// angle bisector
pt p=l^m;
return ln(p, p+l.pq.unit()+m.pq.unit());
}
ln bisec(pt p, pt q){ /// segment bisector (2D) (mediatriz)
return ln((p+q)*.5,p).rot(ccw90);
}
pt perp(pt p) {return {-p.y, p.x};}
struct circle {
pt o; double r;
circle(pt o, double r):o(o),r(r){}
circle(pt x, pt y, pt z){o=bisec(x,y)^bisec(x,z);r=(o-x).norm();}///circumcircle
bool has(pt p){return (o-p).norm()<r-eps;}
vector<pt> operator^(circle c){ // ccw
vector<pt> s;
double d = (o - c.o).norm();
if(d > r+c.r+eps || d+min(r,c.r)+eps < max(r,c.r)) return s;
double x = (d*d - c.r*c.r + r*r)/(2*d);
double y = sqrt(r*r - x*x);
pt v = (c.o - o)/d;
s.pb(o + v*x - v.rot(ccw90)*y);
if(y>eps) s.pb(o + v*x + v.rot(ccw90)*y);
return s;
}
vector<pt> operator^(ln l){
vector<pt> s;
pt p=l.proj(o);
double d=(p-o).norm();
if(d-eps>r)return s;
if(abs(d-r)<=eps){s.pb(p);return s;}
d=sqrt(r*r-d*d);
s.pb(p+l.pq.unit()*d);
s.pb(p-l.pq.unit()*d);
return s;
}
vector<pt> tang(pt p){
double d = sqrt((p-o).norm2()-r*r);
return *this^circle(p,d);
}
vector<pt> Tang(pt p){
pt o1 = o, o2 = p;
double r1 = r, r2 = 0;
pt d = o2-o1;
double dr = r1-r2, d2 = d.norm2(), h2 = d2-dr*dr;
vector<pt> out;
for (double sign : {-1,1}) {
pt v = (d*dr + perp(d)*sqrt(h2)*sign)/d2;
out.pb(o1 + (v*r1));
}
return out;
}
bool in(circle c){ // non strict
double d = (o-c.o).norm();
return d+r <= c.r+eps;
}
double intertriangle(pt a, pt b){ // area of intersection with oab
if(abs((o-a)%(o-b))<=eps)return 0.;
vector<pt> q = {a}, w = *this^ln(a,b);
if(sz(w)==2) for(auto p:w) if((a-p)*(b-p)<-eps) q.pb(p);
q.pb(b);
if(sz(q)==4 && (q[0]-q[1])*(q[2]-q[1])>eps) swap(q[1],q[2]);
double s=0;
forn(i, sz(q)-1){
if(!has(q[i]) || !has(q[i+1])) s+=r*r*(q[i]-o).angle(q[i+1]-o)/2;
else s+=abs((q[i]-o)%(q[i+1]-o)/2);
}
return s;
}
};
double orient(pt a, pt b, pt c){ ///C: >0 left, ==0 on AB, <0 right
return (b-a)%(c-a);
}
double small_angle(pt p, pt q){ ///[0, pi] ([0, 180])
return acos(max(-1.0, min((p*q)/(p.norm()*q.norm()), 1.0)));
}
double dir_ang_CCW(pt a, pt b, pt c){ ///Vertex = B, from BA -> BC (CCW)
if(orient(a,b,c) <= 0){
return small_angle(a-b, c-b);
} else{
return 2*pi - small_angle(a-b, c-b);
}
}
double calc(double m){
double xx = nor*cos(a-m), yy = nor*sin(a-m);
assert(yy >= 0);
pt p(xx, yy), cen(0, r);
circle c(cen, r);
if(c.has(p)) return 1e9;
auto pts = c.Tang(p);
pt best, o(0,0);
if(sz(pts) > 1){
if(dir_ang_CCW(o, cen, pts[0]) > dir_ang_CCW(o, cen, pts[1]))
best = pts[1];
else
best = pts[0];
} else if(isnan(pts[0].x) || isnan(pts[0].y))
best = p;
else
best = pts[0];
double ans = m/w + (dir_ang_CCW(o, cen, best)*r + (p - best).norm())/v;
//d(m/w);d(ans);d(dir_ang_CCW(o, cen, best)*r);d((p - best).norm());
pt b = p - best;
//d(pts[0].x); d(best.y);d(sz(pts));
return ans;
}
double solve1(){
cin >> x >> y;
y = abs(y);
cin >> v >> w;
r = v/w;
a = atan2(y, x);
assert(a >= 0 && a <= pi);
nor = sqrt(x*x+y*y);
double l= 0, r=a, ans = min(calc(l), calc(r)), inf = 1e9;
//d(l); d(r);d(calc(a));d(calc(l));
ans = min({ans,calc(l), calc(r)});
while(r-l > eps){
double m1 = l + (r-l)/3.0, m2= l+ 2*(r-l)/3.0;
double v1 = calc(m1), v2 = calc(m2);
//cout << m1 << " = " << v1 << ", " << m2 << " = " << v2 << el;
if(v1 == inf && v2 == inf){
//d("sizas");
double vl = calc(l), vr = calc(r);
assert(vl < inf || vr < inf);
if(calc(r) < inf){
l = m2;
} else{
r = m1;
}
} else if(v2 < v1){
l = m1;
} else{
r = m2;
}
}
//cout<<el;d(l); d(r);d(calc(a));d(calc(l));
ans = min({ans,calc(l), calc(r)});
return ans;
}
int main(){
//ios_base::sync_with_stdio(false);
//cin.tie(NULL); cout.tie(NULL);
cout << setprecision(10) << fixed;
double a1 = solve1();
cout << a1 << el;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 4220kb
input:
45 179 0.94 3.34
output:
196.4571416878
result:
ok found '196.45714', expected '196.45714', error '0.00000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 4212kb
input:
365 243 1.55 0.15
output:
283.1207010009
result:
ok found '283.12070', expected '283.12070', error '0.00000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
356 -176 0.18 0.71
output:
2206.2986086528
result:
ok found '2206.29861', expected '2206.29861', error '0.00000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 4236kb
input:
326 -350 0.14 2.01
output:
3416.5110771656
result:
ok found '3416.51108', expected '3416.51108', error '0.00000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4264kb
input:
-360 -428 0.65 0.28
output:
864.9603835189
result:
ok found '864.96038', expected '864.96038', error '0.00000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 4244kb
input:
-419 233 0.20 0.74
output:
2399.3423143047
result:
ok found '2399.34231', expected '2399.34231', error '0.00000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
365 288 0.91 1.47
output:
510.9559101916
result:
ok found '510.95591', expected '510.95591', error '0.00000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4044kb
input:
-39 245 0.93 0.29
output:
269.2925950071
result:
ok found '269.29260', expected '269.29260', error '0.00000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4140kb
input:
66 461 2.17 0.32
output:
215.9964563815
result:
ok found '215.99646', expected '215.99646', error '0.00000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 4156kb
input:
476 380 0.40 0.26
output:
1522.8868326091
result:
ok found '1522.88683', expected '1522.88683', error '0.00000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 4216kb
input:
-459 -314 0.13 0.51
output:
4280.9215740274
result:
ok found '4280.92157', expected '4280.92157', error '0.00000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 4236kb
input:
-38 -31 0.30 0.02
output:
244.0422809796
result:
ok found '244.04228', expected '244.04228', error '0.00000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 4280kb
input:
-282 -57 0.50 0.01
output:
778.3327435529
result:
ok found '778.33274', expected '778.33274', error '0.00000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 4220kb
input:
-261 -155 0.20 0.02
output:
1598.8862728257
result:
ok found '1598.88627', expected '1598.88627', error '0.00000'
Test #15:
score: 0
Accepted
time: 2ms
memory: 4240kb
input:
-135 47 0.68 0.01
output:
415.1412675016
result:
ok found '415.14127', expected '415.14127', error '0.00000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
262 0 0.03 0.28
output:
8733.3333333333
result:
ok found '8733.33333', expected '8733.33333', error '0.00000'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4340kb
input:
-10 10 1.00 0.10
output:
31.4159265359
result:
ok found '31.41593', expected '31.41593', error '0.00000'
Test #18:
score: 0
Accepted
time: 0ms
memory: 4176kb
input:
-20 0 1.00 0.10
output:
43.9724223676
result:
ok found '43.97242', expected '43.97242', error '0.00000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 4152kb
input:
-18 112 1.00 0.10
output:
121.1797455767
result:
ok found '121.17975', expected '121.17975', error '0.00000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
-18 112 0.10 10.00
output:
1134.4450922035
result:
ok found '1134.44509', expected '1134.44509', error '0.00000'
Test #21:
score: 0
Accepted
time: 2ms
memory: 4244kb
input:
-999 112 0.01 10.00
output:
100526.0703125447
result:
ok found '100526.07031', expected '100526.07031', error '0.00000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 4204kb
input:
-999 112 10.00 0.01
output:
355.6584290334
result:
ok found '355.65843', expected '355.65843', error '0.00000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4284kb
input:
-1000 0 0.01 0.01
output:
100214.2092653632
result:
ok found '100214.20927', expected '100214.20927', error '0.00000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 4132kb
input:
-1000 0 10.00 10.00
output:
100.2142092654
result:
ok found '100.21421', expected '100.21421', error '0.00000'
Test #25:
score: 0
Accepted
time: 2ms
memory: 4272kb
input:
-1 0 10.00 10.00
output:
0.3665191430
result:
ok found '0.36652', expected '0.36652', error '0.00000'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4144kb
input:
-1 0 0.01 10.00
output:
100.2142092654
result:
ok found '100.21421', expected '100.21421', error '0.00000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 4232kb
input:
-1 0 10.00 0.01
output:
314.2092654039
result:
ok found '314.20927', expected '314.20927', error '0.00000'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3976kb
input:
1000 -1 10.00 0.01
output:
100.0000500167
result:
ok found '100.00005', expected '100.00005', error '0.00000'
Test #29:
score: 0
Accepted
time: 2ms
memory: 4216kb
input:
1000 -1 0.01 10.00
output:
100000.0499999875
result:
ok found '100000.05000', expected '100000.05000', error '0.00000'
Test #30:
score: 0
Accepted
time: 2ms
memory: 4216kb
input:
-862 -92 9.24 0.02
output:
209.2528658706
result:
ok found '209.25287', expected '209.25287', error '0.00000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 4252kb
input:
-22 -8 0.24 0.02
output:
200.3014034502
result:
ok found '200.30140', expected '200.30140', error '0.00000'
Test #32:
score: 0
Accepted
time: 2ms
memory: 4172kb
input:
-574 -49 3.21 0.01
output:
413.7694710348
result:
ok found '413.76947', expected '413.76947', error '0.00000'
Test #33:
score: 0
Accepted
time: 2ms
memory: 4240kb
input:
-693 -228 7.62 0.02
output:
200.3083419730
result:
ok found '200.30834', expected '200.30834', error '0.00000'
Test #34:
score: 0
Accepted
time: 2ms
memory: 4220kb
input:
315 282 9.67 0.02
output:
59.1338985736
result:
ok found '59.13390', expected '59.13390', error '0.00000'