Submission #47550

#	Time	Username	Problem	Language	Result	Execution time	Memory
47550		fallingstar	Experiments with Gorlum (IZhO13_expgorl)	C++17	100 / 100	6 ms	648 KiB

expgorl

/**
    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}; else
        delta[i] = pre;
    }

    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;
}

• Subtask 1: 100 / 100