題目描述：
有個星球起始位置是（xp,yp），繞原點以速度Vp做勻速圓周運動。不明物體起始位置（x,y），速度為V(V>Vp)。這個物體可以隨意移動，但是任何時刻與原點的距離不能小于r。請問這個物體想要與星球位置重合的最少時間是多少？
吐槽：
1. 這么猥瑣的計算幾何居然被我捉掉了真是讓我不得不單獨拿出一篇隨筆來寫阿。。。。。。。。
2. 其實是參照bmerry大神的代碼的。。。。。。。。。。
算法分析：
二分時間（至于為何可以二分就不講了），先用二維仿射幾何計算出星球的新位置P。
再計算不明物體是否可以在這個時間內(nèi)運動到那個新位置處。
如果二者連線形成的線段到原點距離不小于r。那么直接做直線運動。
如果小于r， 判斷是否和r的內(nèi)圓相交。
如果相交的話，求出四條切線。 切線的線段長是固定的，要在小圓上選擇一個最優(yōu)的弧。
因為切點只有四個，直接枚舉即可。
1 #include<iostream>
2 #include<complex>
3 #include<cmath>
4 using namespace std;
5 #define eps 1e-9
6 typedef complex <double> pnt;
7 const double PI = acos(-1);
8 static double dot (const pnt& a, const pnt& b) { return real(conj(a) * b);}
9 static double cross(const pnt&a, const pnt& b) { return imag(conj(a) * b);}
10 inline void chkmin(double &a,const double b){ if(a>b) a = b;}
11 double dist(pnt a, pnt b,double r){
12 double ab = abs(a-b);
13 if(ab < eps) return ab;
14 if(abs(cross(a ,a-b) / ab) >= r) return ab;
15 if(dot ( -a, b-a) < 0.0 || dot(-b, a-b) <0.0) return ab;
16 // cout<<a<<" "<<dot(a,a)<<" "<<r*r<<endl;
17 double as = sqrt(dot(a,a) - r*r);
18 double bs = sqrt(dot(b,b) - r*r);
19 double a_ang = arg(pnt(r,as));
20 double b_ang = arg(pnt(r,bs));
21 double A[2] = {arg(a) + a_ang, arg(a) - a_ang};
22 double B[2] = {arg(b) + b_ang, arg(b) - b_ang};
23 double ans = PI*2;
24 for(int i=0;i<2;i++)
25 for(int j=0;j<2;j++){
26 double ang = abs(A[i] - B[j]);
27 while(ang > PI*2) ang -= PI*2;
28 if(ang > PI) ang = 2*PI - ang;
29 chkmin(ans , ang);
30 }
31 // cout<<as<<" "<<bs<<" "<<r*ans<<endl;
32 return as + bs + r * ans;
33 }
34 int main(){
35 double xp,yp,vp,x,y,v,rp;
36 while(cin >> xp >> yp >> vp >> x >> y >> v >> rp){
37 pnt p1 = pnt(xp,yp);
38 pnt p0 = pnt(x,y);
39 double l = 0, r = 1e9;
40 double R = abs(p1);
41 while(abs(r-l) > eps){
42 double t = (l+r) * 0.5;
43 pnt P = p1 * exp(pnt(0,t*vp / R));
44 double d = dist(p0,P,rp);
45 // cout<<P<<endl;
46 // cout<<l<<" "<<r<<" "<<t<<" "<<d<<endl;
47 if(d <= v*t) r = t;
48 else l = t;
49 }
50 cout.precision(9);
51 cout << l << endl;
52 }
53 }
54
posted on 2012-06-23 19:26
西月弦 閱讀(490)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告