#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
using llong = long long;
struct Vec
{
llong x, y;
llong len() const { return x * x + y * y; }
Vec operator-() const { return {-x, -y}; }
};
Vec operator+(const Vec& a, const Vec& b) { return {a.x + b.x, a.y + b.y}; }
Vec operator-(const Vec& a, const Vec& b) { return a + -b; }
Vec operator*(llong k, const Vec& a) { return {k * a.x, k * a.y}; }
bool operator<(const Vec& a, const Vec& b) { return a.len() < b.len(); }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int k;
cin >> k;
string temp;
cin >> temp;
Vec s, e;
cin >> e.x >> e.y >> s.x >> s.y;
vector<Vec> a(temp.length());
for (int i = 0; i < temp.length(); ++i)
{
if (i) a[i] = a[i - 1];
else a[i] = {0, 0};
if (temp[i] == 'L') --a[i].y;
else if (temp[i] == 'R') ++a[i].y;
else if (temp[i] == 'U') --a[i].x;
else if (temp[i] == 'D') ++a[i].x;
}
Vec mn = e + -s, mx = e + -s;
for (int i = 0; i < a.size(); ++i)
{
auto Go = [&a, &i, &s, &e](int p) -> Vec { return e - (s + p * a.back() + a[i]); };
int l = 0, r = k - 1;
int m = -1;
while (l <= r)
{
int curm = (l + r) / 2;
if (Go(curm) < Go(curm - 1))
{
m = curm;
l = curm + 1;
}
else
r = curm - 1;
}
mx = max(mx, Go(0));
mx = max(mx, Go(k - 1));
#ifdef MANSON
cerr << "i: " << i << ", mx = " << mx.len() << '\n';
#endif
if (m != -1)
mn = min(mn, Go(m));
if (m + 1 <= k - 1)
mn = min(mn, Go(m + 1));
}
cout.precision(10);
cout << fixed << sqrt(mn.len()) << ' ' << sqrt(mx.len());
}
Compilation message
expgorl.cpp: In function 'int main()':
expgorl.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < temp.length(); ++i)
~~^~~~~~~~~~~~~~~
expgorl.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); ++i)
~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
