#include<iostream>
#include<vector>
#include<iomanip>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
struct Vector {
int x, y;
Vector() {
x = 0, y = 0;
}
Vector(int a, int b) {
x = a, y = b;
}
};
Vector operator+(const Vector& a, const Vector& b) {
Vector ans;
ans.x = a.x + b.x;
ans.y = a.y + b.y;
return ans;
}
Vector operator*(const Vector& a, int k) {
Vector ans;
ans.x = a.x * k;
ans.y = a.y * k;
return ans;
}
int getdist(Vector a, int x, int y) {
//cout << a.x << endl;
return ((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
}
int32_t main() {
int k;
cin >> k;
k--;
string s;
cin >> s;
int n = s.size();
int stx, sty, finx, finy;
cin >> stx >> sty >> finx >> finy;
finx -= stx;
finy -= sty;
vector<Vector> a(n + 1);
for (int i = 0; i < n; ++i) {
a[i + 1] = a[i];
if (s[i] == 'L') {
a[i + 1].x--;
}
if (s[i] == 'R') {
a[i + 1].x++;
}
if (s[i] == 'F') {
a[i + 1].y++;
}
if (s[i] == 'B') {
a[i + 1].y--;
}
if (s[i] == 'I') {
//do nothing
}
}
int mind = 1e17, maxd = -1e17;
for (int i = 0; i < n + 1; ++i) {
int tl = 0, tr = k + 1;
while (tl < tr - 2) {
int tm1 = tl + (tr - tl) / 3;
int tm2 = tr - (tr - tl) / 3;
Vector a1 = (a.back() * tm1) + a[i];
Vector b1 = (a.back() * tm2) + a[i];
int d1 = getdist(a1, finx, finy);
int d2 = getdist(b1, finx, finy);
if (d1 < d2) tl = tm1;
else tr = tm2;
}
int tm = (tl + tr) >> 1;
Vector a1 = (a.back() * tm) + a[i];
tm++;
int d1 = getdist(a1, finx, finy);
if (tm -1 <= k) {
mind = min(mind, d1);
maxd = max(maxd, d1);
}
a1 = (a.back() * tm) + a[i];
d1 = getdist(a1, finx, finy);
if (tm <= k) {
mind = min(mind, d1);
maxd = max(maxd, d1);
}
tm = 0;
a1 = (a.back() * tm) + a[i];
d1 = getdist(a1, finx, finy);
mind = min(mind, d1);
maxd = max(maxd, d1);
tm = k;
a1 = (a.back() * tm) + a[i];
d1 = getdist(a1, finx, finy);
mind = min(mind, d1);
maxd = max(maxd, d1);
}
for (int i = 0; i < n + 1; ++i) {
int tl = 0, tr = k + 1;
while (tl < tr - 2) {
int tm1 = tl + (tr - tl) / 3;
int tm2 = tr - (tr - tl) / 3;
Vector a1 = (a.back() * tm1) + a[i];
Vector b1 = (a.back() * tm2) + a[i];
int d1 = getdist(a1, finx, finy);
int d2 = getdist(b1, finx, finy);
if (d1 > d2) tl = tm1;
else tr = tm2;
}
int tm = (tl + tr) >> 1;
Vector a1 = (a.back() * tm) + a[i];
tm++;
int d1 = getdist(a1, finx, finy);
if (tm-1 <= k) {
//cout << tm << endl;
mind = min(mind, d1);
maxd = max(maxd, d1);
}
a1 = (a.back() * tm) + a[i];
d1 = getdist(a1, finx, finy);
if (tm <= k) {
//cout << tm << endl;
mind = min(mind, d1);
maxd = max(maxd, d1);
}
tm = 0;
a1 = (a.back() * tm) + a[i];
d1 = getdist(a1, finx, finy);
mind = min(mind, d1);
maxd = max(maxd, d1);
tm = k;
a1 = (a.back() * tm) + a[i];
d1 = getdist(a1, finx, finy);
mind = min(mind, d1);
maxd = max(maxd, d1);
}
cout << setprecision(20);
cout << sqrt(mind + 0.0) << ' ' << sqrt(maxd + 0.0) << endl;
//cout << getdist(a[1] * 2, finx, finy);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
