답안 #4802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4802 2014-01-04T08:03:44 Z tncks0121 생물 실험 (IZhO13_expgorl) C++
0 / 100
0 ms 1108 KB
#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;
}
# 결과 실행 시간 메모리 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