제출 #16919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16919		murat	생물 실험 (IZhO13_expgorl)	C++98	0 / 100	1 ms	2008 KiB

expgorl

#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, x, y, a, b;
vector< pii > 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 = 1, 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 + 500, n);
    bas = max(1, bas - 500);
    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 >> x >> y >> a >> b;

    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] == 'D') y--;
        if(str[i] == 'U') y++;
    } v.pb(mp(x, y));

    x = as - x;
    y = ad - y;

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

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

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

    return 0;
}

• Subtask 1: 0 / 100