If the missing number is in the command "fd" or "bk", then simulate the walk until "?" (store the coordinates in (xx,yy) ), then simulate the walk after "?" (starting from (0,0), then we finally reach (x,y), then move the coordinate system to make final point (0,0), hence the point where we started is (-x, -y)). Finally the answer is sqrt ( (xx+x)*(xx+x) + (yy+y)*(yy+y) ).
Is there something wrong with the logic or it is precision problem?
My code:
Code: Select all
#define For(i,b) for(int i = 0; i < (int)b; ++i)
#define Fori(i,a,b) for(int i = a; i < (int)b; ++i)
#define mp make_pair
const long double EPS = 1e-9L;
const long double PI = acos(-1.0);
#define rad(a) ((1.*(a)*PI)/180.)
#define sqr(a) ((a)*(a))
using namespace std;
typedef long long ll;
long double dist(long double x1, long double y1, long double x2, long double y2)
{
return sqrt(sqr(x1-x2)+sqr(y1-y2));
}
ll f(ll val)
{
return ((labs(val)/360)+1) * 360;
}
pair<string, ll> a[1010];
ll n,idx,degree;
pair<long double,long double> go()
{
ll deg=0;
long double x=0,y=0;
For(i,n)
{
string s;ll r;
s=a[i].first;
r=a[i].second;
if(r==-1) r = degree;
// db(x),db(y);
switch(s[0])
{
case 'f': x+=1.*r*cos(rad(deg)); y+=1.*r*sin(rad(deg));
break;
case 'b': x+=1.*r*cos(rad((deg+180)%360)); y+=1.*r*sin(rad((deg+180)%360));
break;
case 'l': deg = (deg+r) % 360;
break;
case 'r':deg = (deg-r+f(r)) % 360;
break;
default:
break;
}
// db(deg),db(x),db(y);
}
return mp(x,y);
}
string itos (int i) {stringstream s; s << i; return s.str();}
ll stoi (string s) {istringstream in(s); ll ret; in >> ret; return ret;}
int main ()
{
int t;
cin>>t;
For(z,t)
{
scanf("%lld\n",&n);
ll res=-1;
string s,cmd,x;
idx=-1;
For(i,n)
{
getline(cin,s);
istringstream in(s);
in>>cmd>>x;
if(x=="?")
{
a[i]=mp(cmd,-1);
idx=i;
}
else
{
a[i]=mp(cmd,stoi(x));
}
}
if((a[idx].first=="lt") || (a[idx].first=="rt"))
{
for(degree=0;degree<360;++degree)
// degree=90;
{
// a[idx].second=degree;
pair<long double,long double> cur = go();
// db(cur.first),db(cur.second);
if(fabs(cur.first)<EPS && fabs(cur.second)<EPS)
{
res=degree;
goto L;
}
}
}
else
{
ll deg=0;
long double x=0,y=0;
For(i,idx)
{
string s;ll r;
s=a[i].first;
r=a[i].second;
// if(r==-1) r = degree;
switch(s[0])
{
case 'f': x+=1.*r*cos(rad(deg)); y+=1.*r*sin(rad(deg));
break;
case 'b': x+=1.*r*cos(rad((deg+180)%360)); y+=1.*r*sin(rad((deg+180)%360));
break;
case 'l': deg = (deg+r) % 360;
break;
case 'r':deg = (deg-r+f(r)) % 360;
break;
default:
break;
}
// db(deg),db(x),db(y);
}
long double xx=x,yy=y;
x=0,y=0;
// int d=deg;
Fori(i,idx+1,n)
{
string s;ll r;
s=a[i].first;
r=a[i].second;
// if(r==-1) r = degree;
switch(s[0])
{
case 'f': x+=1.*r*cos(rad(deg)); y+=1.*r*sin(rad(deg));
break;
case 'b': x+=1.*r*cos(rad((deg+180)%360)); y+=1.*r*sin(rad((deg+180)%360));
break;
case 'l': deg = (deg+r) % 360;
break;
case 'r':deg = (deg-r+f(r)) % 360;
break;
default:
break;
}
// db(deg),db(x),db(y);
}
long double X = -1. * x, Y = -1. * y;
res = (ll)dist(X,Y,xx,yy);
} // of else
L: cout<<res<<endl;
}
return 0;
}