Submission #16922

#	Time	Username	Problem	Language	Result	Execution time	Memory
16922		erdemkiraz	Experiments with Gorlum (IZhO13_expgorl)	C++98	100 / 100	11 ms	3408 KiB

expgorl

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e5 + 5;

int k, n;
int dx[300], dy[300];
double cx[N], cy[N];
double lx, ly, kx, ky;
char s[N];

double dist(double x, double y, double a, double b) {
    return sqrt((x - a) * (x - a) + (y - b) * (y - b));
}

double ternary(int i) {
    int l = 0, r = k;
    while(r - l > 5) {
        int m1 = (l + l + r) / 3;
        int m2 = (l + r + r) / 3;
        double d1 = dist(lx, ly, cx[i] + kx * m1, cy[i] + ky * m1);
        double d2 = dist(lx, ly, cx[i] + kx * m2, cy[i] + ky * m2);
        if(d1 < d2)
            r = m2;
        else
            l = m1;
    }
    double ans = linf;
    while(l <= r) {
        double d = dist(lx, ly, cx[i] + kx * l, cy[i] + ky * l);
        ans = min(ans, d);
        l++;
    }
    return ans;
}

int main() {

    scanf("%d", &k);

    k--;

    scanf("%s", s + 1);

    n = strlen(s + 1);

    scanf("%lf %lf", &lx, &ly);

    scanf("%lf %lf", cx, cy);

    dx['L'] = -1;
    dx['R'] = +1;
    dy['F'] = +1;
    dy['B'] = -1;

    double distInit = dist(lx, ly, cx[0], cy[0]);

    double mn = distInit, mx = distInit;

    for(int i = 1; i <= n; i++) {
        cx[i] = cx[i - 1] + dx[s[i]];
        cy[i] = cy[i - 1] + dy[s[i]];
        kx += dx[s[i]];
        ky += dy[s[i]];
    }

    for(int i = 0; i <= n; i++) {
        mx = max(mx, dist(lx, ly, cx[i], cy[i]));
        mx = max(mx, dist(lx, ly, cx[i] + kx * k, cy[i] + ky * k));
        mn = min(mn, ternary(i));
    }

    printf("%.12lf %.12lf\n", mn, mx);

    return 0;

}

• Subtask 1: 100 / 100