oj.uz

답안 #8200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
8200 2014-09-06T14:42:50 Z gs14004 생물 실험 (IZhO13_expgorl) C++
5 / 100
 1000 ms 1268 KB 
#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pi;

int k;
char s[10005];
pi afterCycle, a[10005], laser, ainta, mp[150];
lint minv, maxv;

lint dist(pi x, pi y){
    return (y.second - x.second)*(y.second - x.second) + (y.first - x.first)*(y.first - x.first);
}
pi mv(pi x, int time){return pi(x.first + afterCycle.first * time, x.second + afterCycle.second * time);}
lint f(pi x, int t){return dist(laser,mv(x,t));}

void input(){
    scanf("%d %s",&k,s);
    scanf("%lld %lld %lld %lld",&laser.first,&laser.second,&ainta.first,&ainta.second);
    mp['I'] = pi(0ll,0ll);
    mp['L'] = pi(-1ll,0ll);
    mp['R'] = pi(1ll,0ll);
    mp['B'] = pi(0ll,-1ll);
    mp['F'] = pi(0ll,1ll);
}

int main(){
    input();
    minv = maxv = dist(laser,ainta);
    pi x = ainta;
    for (int i=0; s[i]; i++) {
        x.first += mp[s[i]].first;
        x.second += mp[s[i]].second;
        a[i] = x;
    }
    afterCycle = pi(x.first - ainta.first,x.second - ainta.second);
    for (int i=0; s[i]; i++) {
        int s = 0, e = k-1, m1, m2;
        while (s != e) {
            m1 = (2*s + e)/3;
            m2 = (s + 2*e)/3;
            if(f(a[i],m1) < f(a[i],m2)) s = m1;
            else e = m2;
        }
        minv = min(minv,f(a[i],s));
        maxv = max(maxv,f(a[i],0));
        maxv = max(maxv,f(a[i],k-1));
    }
    printf("%lf\n%lf",sqrt(minv),sqrt(maxv));
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 1264 KB Program timed out
2 Execution timed out 1000 ms 1264 KB Program timed out
3 Execution timed out 1000 ms 1264 KB Program timed out
4 Execution timed out 1000 ms 1264 KB Program timed out
5 Execution timed out 1000 ms 1264 KB Program timed out
6 Execution timed out 1000 ms 1264 KB Program timed out
7 Execution timed out 1000 ms 1264 KB Program timed out
8 Execution timed out 1000 ms 1264 KB Program timed out
9 Execution timed out 1000 ms 1264 KB Program timed out
10 Execution timed out 1000 ms 1264 KB Program timed out
11 Execution timed out 1000 ms 1264 KB Program timed out
12 Execution timed out 1000 ms 1264 KB Program timed out
13 Execution timed out 1000 ms 1264 KB Program timed out
14 Execution timed out 1000 ms 1264 KB Program timed out
15 Execution timed out 1000 ms 1264 KB Program timed out
16 Execution timed out 1000 ms 1264 KB Program timed out
17 Correct 0 ms 1268 KB Output is correct
18 Execution timed out 1000 ms 1264 KB Program timed out
19 Execution timed out 1000 ms 1264 KB Program timed out
20 Execution timed out 1000 ms 1264 KB Program timed out