/**
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];
TPoint pre = (i ? delta[i - 1] : TPoint {0, 0});
if (ch == 'L') delta[i] = pre + TPoint {-1, 0}; else
if (ch == 'R') delta[i] = pre + TPoint {1, 0}; else
if (ch == 'F') delta[i] = pre + TPoint {0, 1}; else
if (ch == 'B') delta[i] = pre + 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));
for (int i = 1; i <= k; ++i)
for (int j = 0; j < s.size(); ++j)
{
TPoint cur = gorlum + delta[s.size() - 1] * (i - 1) + delta[j];
minDist = min(minDist, Dist(laser, cur));
maxDist = max(maxDist, Dist(laser, cur));
}
cout << setprecision(9) << fixed << minDist << ' ' << maxDist;
return 0;
}
Compilation message
expgorl.cpp: In function 'int main()':
expgorl.cpp:88:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < s.size(); ++j)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
