102. 最遠距離

時間限制1000 ms???? 內存限制 65536 KB????

題目描述

正義的伙伴褋祈和葬儀社的機器人Fuyuneru正在被邪惡的GHQ部隊追殺。眼看著快要逃不掉了，祈就把重要的東西塞到了機器人體內，讓它先跑，自己吸引火力。

假設Fuyuneru帶上東西開始逃跑時所處的點為原點，朝向為正北。操縱FuyuNeru的指令有如下四種：

right X: X是1-359之間的整數，Fuyuneru的前進方向順時針轉X度。

left X: X是1-359之間的整數，Fuyuneru的前進方向逆時針轉X度。

forward X: X是整數(0<=X<=1000)，Fuyuneru向當前朝向前進X米。

backward X: X是整數(0<=X<=1000)，Fuyuneru向當前朝向后退X米。

現在祈向Fuyuneru體內輸入了N(1<=N<=50)個這樣的指令。可是由于此前Fuyuneru被GHQ部隊擊中，它出了一點小問題：這N個指令執行的順序是不確定的。

問：Fuyuneru最遠可能逃出多遠？

即，Fuyuneru在執行完N條指令之后，距離原點最遠的可能距離是多少？

輸入格式

第一行是一個整數T，代表測試數據有T組。

每組測試數據中，第一行是一個整數N，代表指令有N條；

隨后緊跟N行，每一行代表一個指令（格式保證是上述四種中的一種，數據保證合法）

輸出格式

對于每組數據，輸出一行：最遠的可能逃亡距離，精確到小數點后3位。

輸入樣例

3 3 forward 100 backward 100 left 90 4 left 45 forward 100 right 45 forward 100 6 left 10 forward 40 right 30 left 10 backward 4 forward 4

輸出樣例

141.421 200.000 40.585

?

最遠距離為，向前走之后，找到一個向后走的時候向前走的方向盡可能處在180°上的方向。

比如，向前走100米，然后向右轉180°，然后向后走100米，然后隨意旋轉，這樣就距離起點最遠，200米。

所以問題轉化為，找到一種旋轉組合，使得盡可能旋轉180°。

然后利用a^2+b^2-2abcosC=c^2求出最遠距離

?

對于求出旋轉角度組合，設向右為正，假設輸入順序：60°，30°，10°，等等

我們讀入60°的時候，從（0+60°）-（360°+60°）開始枚舉，首先標記60°為訪問過，vis[60]=1，即我們可以旋轉出60°這個角度來，然后訪問余下的角度，如果訪問過x°，if(vis[x]==1)，那么我們標記x+60°為也訪問過，即x+60°這個角度也是可以被訪問到的，vis[x+60]=1。

比如，當我們按順序第二個讀入30°的時候，vis[30]=1，在（0+60°）-（360°+60°）枚舉的過程中，枚舉到30°+30°的時候，因為vis[30+30]==1，所以，vis[60+30]=1。

然后我們只要不斷更新，最接近180的vis[]，然后計算即可。

?

?

#include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<set> #define Pi acos(-1.0) using namespace std;double dis(double a,double b,double Ang) {return sqrt(a*a+b*b-2*a*b*cos(Ang/180*Pi)); }int main() {int i,j,t,n,vis[360],val,minA,rec[360];//minA是和180°最接近的角度,vis用來記錄是否可以到達該角度，rec用來記錄當前角度是否被使用過multiset<int>turn; //來存旋轉角度，向右為正int up,down; //前進和后退string s;for(cin>>t;t--;){turn.clear();up=down=0;memset(vis,0,sizeof vis);for(cin>>n;n--;){cin>>s>>val;if(s=="forward")up+=val;else if(s=="backward")down+=val;else{if(s=="right")turn.insert(val);else turn.insert(360-val);}}multiset<int>::iterator it;vis[0]=1;for(it=turn.begin();it!=turn.end();it++){//printf("it:%d\n",*it);memset(rec,0,sizeof rec);for(i=0;i<360;i++){int tmp=(i+*it)%360;if(rec[i]==0&&(vis[i])&&vis[tmp]==0){vis[tmp]=rec[tmp]=1;}}}minA=180; //防止沒有旋轉指令for(i=0;i<360;i++)if(vis[i])if(abs(180-i)<minA)minA=abs(180-i);//printf("minA:%d\n",minA);printf("%.3lf\n",dis(up,down,180-minA));}return 0; }

?

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的北邮OJ 102. 最远距离 北邮2012网研院复试上机题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。