Submission #4802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4802	2014-01-04T08:03:44 Z	tncks0121	Experiments with Gorlum (IZhO13_expgorl)	C++	0 / 100	0 ms	1108 KB

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 - AX, dy = y - AY;
	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(LX, LY);

	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( (LX + DX * f) - AX, (LY + DY * f) - AY );
		lf val_s = hypot( (LX + DX * s) - AX, (LY + DY * s) - AY );
		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( (LX + DX * f) - AX, (LY + DY * f) - AY );
		lf val_s = hypot( (LX + DX * s) - AX, (LY + DY * s) - AY );
		if(val_f < val_s) {
			low = f;
		}else {
			high = s;
		}
	}

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

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

	return 0;
}

Subtask #1

0.0 / 100.0

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