/**
Problem: Experiments with Gorlum
Source: IX Zhautykov Olympiad on Mathematics, Physics and Informatics (IZhO) 2013, day 1, problem A
*/
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#define long long long
using namespace std;
const int N = 1e4 + 2;
const double INF = 1e12;
template<typename T> inline T sqr(T x) { return x * x; }
struct TPoint { int x, y; };
istream &operator >> (istream &inp, TPoint &a)
{
inp >> a.x >> a.y;
return inp;
}
TPoint operator + (TPoint a, TPoint b) { return {a.x + b.x, a.y + b.y}; }
TPoint operator * (TPoint a, int k) { return {a.x * k, a.y * k}; }
double Dist(TPoint a, TPoint b)
{
return sqrt(sqr<long>(a.x - b.x) + sqr<long>(a.y - b.y));
}
int k;
string s;
TPoint laser, gorlum;
TPoint delta[N];
double minDist = INF, maxDist = 0;
double CalMin(int k)
{
double ret = INF;
for (size_t i = 0; i < s.size(); ++i)
{
TPoint cur = gorlum + delta[s.size() - 1] * (k - 1) + delta[i];
ret = min(ret, Dist(laser, cur));
}
return ret;
}
int main()
{
cin >> k >> s;
cin >> laser >> gorlum;
for (size_t i = 0; i < s.size(); ++i)
{
char ch = s[i];
if (ch == 'L') delta[i] = delta[i - 1] + TPoint {-1, 0}; else
if (ch == 'R') delta[i] = delta[i - 1] + TPoint {1, 0}; else
if (ch == 'F') delta[i] = delta[i - 1] + TPoint {0, 1}; else
if (ch == 'B') delta[i] = delta[i - 1] + TPoint {0, -1};
}
minDist = Dist(laser, gorlum);
maxDist = Dist(laser, gorlum);
for (size_t i = 0; i < s.size(); ++i)
{
TPoint cur = gorlum + delta[i];
maxDist = max({maxDist, Dist(laser, cur), Dist(laser, cur + delta[s.size() - 1] * (k - 1))});
}
int lo = 1, hi = k;
while (lo < hi)
{
int mid = (lo + hi) / 2;
double fmid = CalMin(mid), fmid1 = CalMin(mid + 1);
minDist = min({minDist, fmid, fmid1});
if (fmid <= fmid1)
hi = mid;
else
lo = mid + 1;
}
minDist = min(minDist, CalMin(lo));
cout << setprecision(9) << fixed << minDist << ' ' << maxDist;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
