Submission #8103

#	Time	Username	Problem	Language	Result	Execution time	Memory
8103		baneling100	Experiments with Gorlum (IZhO13_expgorl)	C++98	100 / 100	0 ms	1264 KiB

expgorl

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define INF 0x7fffffffffffffff

using namespace std;

long long K, Len, Lx, Ly, Ax, Ay, Vx, Vy, Sx[10001], Sy[10001], MAX, MIN=INF;
char S[10002];

void input(void) {

    scanf("%lld %s %lld %lld %lld %lld",&K,&S[1],&Lx,&Ly,&Ax,&Ay);
    Len=strlen(&S[1]);
}

pair <long long,long long> Order(char T) {

    if(T=='L') return make_pair(-1,0);
    else if(T=='R') return make_pair(1,0);
    else if(T=='F') return make_pair(0,1);
    else if(T=='B') return make_pair(0,-1);
    return make_pair(0,0);
}

void process(void) {

    pair <long long,long long> Temp;
    long long Ex, Ey, Left, Mid1, Mid2, Right, D1, D2;

    Sx[0]=Ax;
    Sy[0]=Ay;
    for(long long i=1 ; i<=Len ; i++) {
        Temp=Order(S[i]);
        Sx[i]=Sx[i-1]+Temp.first;
        Sy[i]=Sy[i-1]+Temp.second;
    }
    Vx=Sx[Len]-Ax;
    Vy=Sy[Len]-Ay;
    for(long long i=0 ; i<=Len ; i++) {
        Ex=Sx[i]+Vx*(K-1);
        Ey=Sy[i]+Vy*(K-1);
        MAX=max(MAX,max((Sx[i]-Lx)*(Sx[i]-Lx)+(Sy[i]-Ly)*(Sy[i]-Ly),(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly)));
        Left=0;
        Right=K-1;
        while(Right-Left>=2) {
            Mid1=(2*Left+Right)/3;
            Mid2=(Left+2*Right)/3;
            Ex=Sx[i]+Vx*Mid1;
            Ey=Sy[i]+Vy*Mid1;
            D1=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
            Ex=Sx[i]+Vx*Mid2;
            Ey=Sy[i]+Vy*Mid2;
            D2=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
            if(D1<D2)
                Right=Mid2-1;
            else
                Left=Mid1+1;
        }
        Ex=Sx[i]+Vx*Left;
        Ey=Sy[i]+Vy*Left;
        D1=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
        Ex=Sx[i]+Vx*Right;
        Ey=Sy[i]+Vy*Right;
        D2=(Ex-Lx)*(Ex-Lx)+(Ey-Ly)*(Ey-Ly);
        MIN=min(MIN,min(D1,D2));
    }
}

void output(void) {

    printf("%.15lf %.15lf",sqrt(MIN),sqrt(MAX));
}

int main(void) {

    input();
    process();
    output();

    return 0;
}

• Subtask 1: 100 / 100