2012.网研院.Problem D.最远距离-蒲公英云

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

傷城~ 2023-07-22 03:43 51阅读 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);
    }
}