oj.uz

Submission #32221

# Submission time Handle Problem Language Result Execution time Memory
32221 2017-10-04T21:31:00 Z chonka Experiments with Gorlum (IZhO13_expgorl) C++
100 / 100
 9 ms 2808 KB 
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
using namespace std ;

#define MAXN 100007
#define eps 0.00001
int k ;
int n ;
string a ;

int x , y ;
int p , q ;

int dx , dy ;

int prefx[ MAXN ] ;
int prefy[ MAXN ] ;

double get_dist ( int a , int b , int c , int d ) {
    double k = 1.00000 * ( a - c ) * ( a - c ) + 1.0000000 * ( b - d ) * ( b - d ) ;
    return sqrt ( k ) ;
}

double f ( int id , int pos ) {
    int u1 , u2 ;
    u1 = p + dx * id + prefx[ pos ] ;
    u2 = q + dy * id + prefy[ pos ] ;
    return ( get_dist ( x , y , u1 , u2 ) ) ;
}

double get_opt ( int pos ) {
    int l , r , mid1 , mid2 ;
    double ret = f ( 0 , pos ) ;
    l = 0 ;
    r = k - 1 ;
    while ( r - l > 3 ) {
        mid1 = ( 2 * l + r ) / 3 ;
        mid2 = ( l + 2 * r ) / 3 ;
        double ret1 = f ( mid1 , pos ) ;
        double ret2 = f ( mid2 , pos ) ;
        if ( ret1 > ret2 - eps ) { l = mid1 ; }
        else { r = mid2 ; }
    }
    for ( int i = l ; i <= r ; i ++ ) {
        ret = min ( ret , f ( i , pos ) ) ;
    }
    return ret ;
}

void input ( ) {
    cin >> k ;
    cin >> a ;
    n = a.size ( ) ;
    cin >> x >> y >> p >> q ;
}

void solve ( ) {
    int i ;
    dx = dy = 0 ;
    for ( i = 0 ; i < n ; i ++ ) {
        if ( a[ i ] == 'L' ) { dx -- ; }
        if ( a[ i ] == 'R' ) { dx ++ ; }
        if ( a[ i ] == 'F' ) { dy ++ ; }
        if ( a[ i ] == 'B' ) { dy -- ; }
        prefx[ i ] = dx ;
        prefy[ i ] = dy ;
    }
    double mx , mn ;
    mx = mn = get_dist ( x , y , p , q ) ;
    for ( i = 0 ; i < n ; i ++ ) {
        mx = max ( mx , f ( 0 , i ) ) ;
        mx = max ( mx , f ( k - 1 , i ) ) ;
        mn = min ( mn , get_opt ( i ) ) ;
    }
    printf ( "%.12lf %.12lf\n" , mn , mx ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2808 KB Output is correct
2 Correct 0 ms 2808 KB Output is correct
3 Correct 0 ms 2808 KB Output is correct
4 Correct 0 ms 2808 KB Output is correct
5 Correct 0 ms 2808 KB Output is correct
6 Correct 0 ms 2808 KB Output is correct
7 Correct 0 ms 2808 KB Output is correct
8 Correct 0 ms 2808 KB Output is correct
9 Correct 3 ms 2808 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 3 ms 2808 KB Output is correct
12 Correct 6 ms 2808 KB Output is correct
13 Correct 6 ms 2808 KB Output is correct
14 Correct 3 ms 2808 KB Output is correct
15 Correct 6 ms 2808 KB Output is correct
16 Correct 6 ms 2808 KB Output is correct
17 Correct 6 ms 2808 KB Output is correct
18 Correct 6 ms 2808 KB Output is correct
19 Correct 9 ms 2808 KB Output is correct
20 Correct 9 ms 2808 KB Output is correct