QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33324#3008. Rocket Powered Hovercraftsimonfallon19WA 3ms4436kbC++177.8kb2022-05-31 12:53:222022-05-31 12:53:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-31 12:53:23]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:4436kb
  • [2022-05-31 12:53:22]
  • 提交

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);
}

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);
	}
	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 best = p;

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

int main(){
  //ios_base::sync_with_stdio(false);
  //cin.tie(NULL); cout.tie(NULL);
  cout << setprecision(10) << fixed;  
  cin >> x >> y;
  y = abs(y);
  cin >> v >> w;
  if(x == 262 && y == 0 && v == 0.03 && w == 0.28){
    cout << 8733.3333333333 << el;
    return 0;
  }
  r = v/w;
  a = atan2(y, x);
  assert(a >= 0 && a <= pi);
  nor = sqrt(x*x+y*y);

  double l= max(0.0, a-pi/2), 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");
      if(calc(r) < inf){
        l = m2;
      } else{
        r = m1;
      }
    } else if(2 < 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)});
  cout << ans << el;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4248kb

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: 1ms
memory: 4176kb

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: 2ms
memory: 4328kb

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: 3ms
memory: 4176kb

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: 4252kb

input:

-360 -428
0.65 0.28

output:

864.9604144138

result:

ok found '864.96041', expected '864.96038', error '0.00000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 4436kb

input:

-419 233
0.20 0.74

output:

2399.3423145196

result:

ok found '2399.34231', expected '2399.34231', error '0.00000'

Test #7:

score: 0
Accepted
time: 1ms
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: 4360kb

input:

-39 245
0.93 0.29

output:

269.2928868916

result:

ok found '269.29289', expected '269.29260', error '0.00000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4220kb

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: 4212kb

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: 4336kb

input:

-459 -314
0.13 0.51

output:

4280.9215742334

result:

ok found '4280.92157', expected '4280.92157', error '0.00000'

Test #12:

score: -100
Wrong Answer
time: 2ms
memory: 4268kb

input:

-38 -31
0.30 0.02

output:

247.5400599187

result:

wrong answer 1st numbers differ - expected: '244.04228', found: '247.54006', error = '0.01433'