Submission #4804

#	Time	Username	Problem	Language	Result	Execution time	Memory
4804		tncks0121	Experiments with Gorlum (IZhO13_expgorl)	C++98	100 / 100	0 ms	1108 KiB

expgorl

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int L_ = 10005;

int dtx[128], dty[128];

int K;
char S[L_]; int L;
int DX, DY, LX, LY, AX, AY;

ll Rmin, Rmax;

ll dst (ll x, ll y) {
	ll dx = x - LX, dy = y - LY;
	return dx*dx + dy*dy;
}

void update (ll x, ll y) {
	ll d = dst(x, y);
	Rmin = min(Rmin, d);
	Rmax = max(Rmax, d);
}

void get (int t) {
	if(t < 0 || t >= K) return;

	ll x = (ll)AX + (ll)DX * (ll)t, y = (ll)AY + (ll)DY * (ll)t;
	update(x, y);
	for(int i = 0; i < L; i++) {
		x += dtx[S[i]];
		y += dty[S[i]];
		update(x, y);
	}
}

int main() {
	int i, j, k;

	scanf("%d%s", &K, S);
	L = strlen(S);
	scanf("%d%d%d%d", &LX, &LY, &AX, &AY);

	dtx['L'] = -1;
	dtx['R'] =  1;
	dty['B'] = -1;
	dty['F'] =  1;
	for(i = 0; i < L; i++) DX += dtx[S[i]], DY += dty[S[i]];

	Rmin = Rmax = dst(AX, AY);

	lf low, high;
	
	// find min
	low = 0, high = K-1;
	for(k = 0; k < 100; k++) {
		lf f = (low * 2 + high) / 3;
		lf s = (low + high * 2) / 3;
		lf val_f = hypot( (AX + DX * f) - LX, (AY + DY * f) - LY );
		lf val_s = hypot( (AX + DX * s) - LX, (AY + DY * s) - LY );
		if(val_f < val_s) {
			high = s;
		}else {
			low = f;
		}
	}

	for(i = (int)low - 10; i <= (int)low + 10; i++) get(i);

	// find max
	low = 0, high = K - 1;
	for(k = 0; k < 100; k++) {
		lf f = (low * 2 + high) / 3;
		lf s = (low + high * 2) / 3;
		lf val_f = hypot( (AX + DX * f) - LX, (AY + DY * f) - LY );
		lf val_s = hypot( (AX + DX * s) - LX, (AY + DY * s) - LY );
		if(val_f < val_s) {
			low = f;
		}else {
			high = s;
		}
	}

	for(i = (int)low - 10; i <= (int)low + 10; i++) get(i);

	printf("%.15lf %.15lf", sqrt(Rmin), sqrt(Rmax));

	return 0;
}

• Subtask 1: 100 / 100