oj.uz

Submission #16921

# Submission time Handle Problem Language Result Execution time Memory
16921 2015-10-26T13:17:23 Z murat Experiments with Gorlum (IZhO13_expgorl) C++
100 / 100
 62 ms 2264 KB 
#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int n, m;
double x, y, a, b;
vector< pair< double, double > > v;
string str;

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

double take(double a, double b, int xx) {
    return dist(a + (xx-1) * x, b + (xx-1) * y, ::a, ::b);
}

double find_max(double x, double y) {
    return max(take(x, y, 1), take(x, y, n));
}

double find_min(double x, double y) {
    int bas = 0, son = n;
    while(bas + 5 < son) {
        int l = (son - bas + 1) / 3;
        int o1 = bas + l - 1;
        int o2 = min(son, o1 + l - 1);
        if(take(x, y, o1) >= take(x, y, o2))
            bas = o1;
        else
            son = o2;
    }
    son = min(bas + 300, n);
    bas = max(1, bas - 300);
    double mn = 1e18;
    FOR(i, bas, son)
        mn = min(mn, take(x, y, i));
    return mn;
}


int main() {

    ios_base::sync_with_stdio(false);

    cin >> n;

    cin >> str;
    m = str.size();
    str = '0' + str;

    cin >> a >> b >> x >> y;

    int as = x, ad = y;

    FOR(i, 1, m) {
        v.pb(mp(x, y));
        if(str[i] == 'L') x--;
        if(str[i] == 'R') x++;
        if(str[i] == 'B') y--;
        if(str[i] == 'F') y++;
    } v.pb(mp(x, y));

    x = (x - as);
    y = (y - ad);

    double mx = -1e18, mn = 1e18;

    foreach(it, v)
        mx = max(mx, find_max(it->st, it->nd)),
        mn = min(mn, find_min(it->st, it->nd));

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

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1880 KB Output is correct
2 Correct 7 ms 1876 KB Output is correct
3 Correct 6 ms 1876 KB Output is correct
4 Correct 10 ms 1876 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 9 ms 1876 KB Output is correct
7 Correct 8 ms 1876 KB Output is correct
8 Correct 9 ms 1876 KB Output is correct
9 Correct 22 ms 2012 KB Output is correct
10 Correct 36 ms 2264 KB Output is correct
11 Correct 15 ms 2012 KB Output is correct
12 Correct 43 ms 2264 KB Output is correct
13 Correct 51 ms 2264 KB Output is correct
14 Correct 40 ms 2012 KB Output is correct
15 Correct 49 ms 2012 KB Output is correct
16 Correct 34 ms 2264 KB Output is correct
17 Correct 36 ms 2264 KB Output is correct
18 Correct 36 ms 2264 KB Output is correct
19 Correct 38 ms 2264 KB Output is correct
20 Correct 62 ms 2264 KB Output is correct