Submission #32221

#	Time	Username	Problem	Language	Result	Execution time	Memory
32221		chonka	Experiments with Gorlum (IZhO13_expgorl)	C++98	100 / 100	9 ms	2808 KiB

expgorl

#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 / 100