#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
string s;
ld ansmn, ansmx;
int go1[5] = {1, -1, 0, 0, 0};
int go2[5] = {0, 0, 1, -1, 0};
int dir[N];
ld dist(int x1, int y1, int x2, int y2){
return (ld)sqrtl((ld)abs(x1-x2)*abs(x1-x2) + (ld)abs(y1-y2)*abs(y1-y2));
}
int aftergy, aftergx;
pii doit(int dx, int dy, int gx, int gy){
ckmin(ansmn, dist(dx, dy, gx, gy));
ckmax(ansmx, dist(dx, dy, gx, gy));
ld mn = mod*mod, mx = 0.;
for(int i=0;i<n;i++){
gx += go1[dir[i]];
gy += go2[dir[i]];
ckmin(ansmn, dist(dx, dy, gx, gy));
ckmax(ansmx, dist(dx, dy, gx, gy));
ckmin(mn, dist(dx, dy, gx, gy));
ckmax(mx, dist(dx, dy, gx, gy));
}
aftergy = gy;
aftergx = gx;
return {mn, mx};
}
void solve(int test_case){
cout << fixed << setprecision(12);
int i, j;
cin >> k;
cin >> s;
n = s.length();
for(i=0;i<n;i++){
if(s[i] == 'L')dir[i] = 1;
if(s[i] == 'R')dir[i] = 0;
if(s[i] == 'F')dir[i] = 2;
if(s[i] == 'B')dir[i] = 3;
if(s[i] == 'I')dir[i] = 4;
}
int dx, dy;
int gx, gy;
cin >> dx >> dy;
cin >> gx >> gy;
ansmn = mod*mod;
ansmx = 0.;
int deltax, deltay;
pii I_DONT_EVEN_NEED_IT = doit(dx, dy, gx, gy);
deltax = aftergx - gx;
deltay = aftergy - gy;
int l = 1, r = k-1;
int itr = 0;
while(l < r){
itr++;
if(itr > 300)break;
int mid = (l+r)/2;
int tox = gx + deltax * mid;
int toy = gy + deltay * mid;
auto [mn1, mx1] = doit(dx, dy, tox, toy);
tox -= deltax;
toy -= deltay;
auto [mn2, mx2] = doit(dx, dy, tox, toy);
if(mn2 < mn1){
r = mid;
}else l = mid;
}
doit(dx, dy, gx+deltax*(k-1), gy+deltay*(k-1));
// cout << l << ' ' << r << '\n';
//~ for(i=0;i<k;i++){
//~ doit(dx, dy, gx, gy);
//~ gx = aftergx;
//~ gy = aftergy;
//~ }
for(i=max(0ll, l-1000); i < min(k, r+1000); i++){
int tox = gx + deltax * i;
int toy = gy + deltay * i;
doit(dx, dy, tox, toy);
}
l = 1, r = k-1;
itr = 0;
while(l < r){
itr++;
if(itr > 300)break;
int mid = (l+r)/2;
int tox = gx + deltax * mid;
int toy = gy + deltay * mid;
auto [mn1, mx1] = doit(dx, dy, tox, toy);
tox -= deltax;
toy -= deltay;
auto [mn2, mx2] = doit(dx, dy, tox, toy);
if(mx2 > mx1){
r = mid;
}else l = mid;
}
for(i=max(0ll, l-1000); i < min(k, r+1000); i++){
int tox = gx + deltax * i;
int toy = gy + deltay * i;
doit(dx, dy, tox, toy);
}
// cout << l << ' ' << r << '\n';
cout << ansmn << ' ' << ansmx << '\n';
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int _T;
cin >> _T;
for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
expgorl.cpp: In function 'void solve(long long int)':
expgorl.cpp:48:9: warning: unused variable 'j' [-Wunused-variable]
48 | int i, j;
| ^
expgorl.cpp:67:6: warning: variable 'I_DONT_EVEN_NEED_IT' set but not used [-Wunused-but-set-variable]
67 | pii I_DONT_EVEN_NEED_IT = doit(dx, dy, gx, gy);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
364 KB |
Output is correct |
| 2 |
Correct |
91 ms |
364 KB |
Output is correct |
| 3 |
Correct |
80 ms |
364 KB |
Output is correct |
| 4 |
Correct |
107 ms |
364 KB |
Output is correct |
| 5 |
Correct |
71 ms |
364 KB |
Output is correct |
| 6 |
Correct |
78 ms |
364 KB |
Output is correct |
| 7 |
Correct |
108 ms |
424 KB |
Output is correct |
| 8 |
Correct |
115 ms |
424 KB |
Output is correct |
| 9 |
Correct |
334 ms |
364 KB |
Output is correct |
| 10 |
Correct |
505 ms |
512 KB |
Output is correct |
| 11 |
Correct |
235 ms |
364 KB |
Output is correct |
| 12 |
Correct |
534 ms |
620 KB |
Output is correct |
| 13 |
Correct |
567 ms |
620 KB |
Output is correct |
| 14 |
Correct |
433 ms |
488 KB |
Output is correct |
| 15 |
Correct |
501 ms |
488 KB |
Output is correct |
| 16 |
Correct |
538 ms |
520 KB |
Output is correct |
| 17 |
Correct |
534 ms |
520 KB |
Output is correct |
| 18 |
Correct |
542 ms |
520 KB |
Output is correct |
| 19 |
Correct |
558 ms |
640 KB |
Output is correct |
| 20 |
Correct |
582 ms |
520 KB |
Output is correct |
