自动搬运

查看原文

来自洛谷，原作者为

	斗神_君莫笑 仙子自无倾慕意，少年何故再添愁？

搬运于2025-08-24 21:39:47，当前版本为作者最后更新于2019-08-15 11:19:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题需要我们求出最长的离原点距离
那么显然我们可以先走完所有的front,
尝试转到一个离180度最近的角度后走back，
问题就转化为了如何求出一通瞎转后离180度最近的角度，

选取任意旋转后满足某条件
这不就是个变形的01背包嘛
按照01的写法枚举出每一种可能达到的角度
然后挨个遍历取出离180最近的角度
最后余弦公式就解决了
注意计算cos的时候要角度转弧度

#include<bits/stdc++.h>
using namespace std;
int a[410],f[20010];
int main(){
	int n;
	cin>>n;
	int x=0,y=0;
	for(int i=1;i<=n;++i){
		string s;cin>>s;
		int dis;cin>>dis;
		if(s=="forward")x+=dis;
		if(s=="backward")y+=dis;
		if(s=="left"){
			dis=dis%360;
			a[dis]++;
			//cout<<dis<<" "<<a[dis]<<endl;
		}
		if(s=="right"){
			dis=dis%360;
			a[360-dis]++;
		}
	}
	f[0]=1;
	for(int i=0;i<360;++i)
		while(a[i]--)
			for(int j=20000;j>=0;--j)
				if(f[j])f[j+i]++;
	int minn=0x7fffffff;
	for(int i=1;i<=20000;++i)
		if(f[i])
			minn=min(minn,abs(i%360-180));
	if(minn==0){
		printf("%d.000000",x+y);
		return 0;
	}
	printf("%.6f",sqrt((double)x*x+(double)y*y-2*(double)x*(double)y*cos((double)(180-minn)*M_PI/180)));
	return 0;
}