2012.网研院.Problem D.最远距离

傷城~ 2023-07-22 03:43 129阅读 0赞

**题目描述**  
正义的伙伴褋祈和葬仪社的机器人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°。  
然后利用a2 \+b2 \-2abcosC=c2求出最远距离

#include<bits/stdc++.h>
    using namespace std;
    const double Pi = acos(-1.0);
    int min(int a,int b) { 
    	return a<b?a:b;
    }
    int main() { 
    	int t,n,x;
    	string op;
    	double ans;
    	cin>>t;
    	while(t--) { 
    		vector<int> ang;//记录角度
    		int vis[360],dp[360];//访问标记 
    		cin>>n;
    		int a=0,b=0;
    		for(int i=0; i<n; i++) { 
    			cin>>op>>x;
    			if(op=="forward") { 
    				a+=x;
    			} else if(op=="backward") { 
    				b+=x;
    			} else if(op=="right") { 
    				ang.push_back(x);
    			} else if(op=="left") { 
    				ang.push_back(360-x);
    			}
    		}
    		memset(vis,0,sizeof(vis));
    		vis[0]=1;//0度 
    		int len=ang.size();
    		int min_value=180;
    		for(int j=0; j<len; j++) { 
    			memset(dp,0,sizeof(dp));
    			for(int i=0; i<360; i++) { 
    				int temp=(i+ang[j])%360;
    				if(vis[i]&&dp[i]==0&&vis[temp]==0) { 
    					vis[temp]=1;
    					dp[temp]=1;
    					min_value=min(min_value,abs(180-temp));
    				}
    			}
    		}
    		//a^2+b^2-2abcosC=c^2求出最远距离
    		double angle=(180-(double)min_value)*Pi/180;
    		ans=sqrt((double)a*(double)a+(double)b*(double)b-2*(double)a*(double)b*cos(angle));
    		printf("%.3lf\n",ans);
    	}
    }