oj.uz

Submission #56114

# Submission time Handle Problem Language Result Execution time Memory
56114 2018-07-10T04:33:37 Z 윤교준(#1582) Mobile (BOI12_mobile) C++11
8 / 100
 1000 ms 8448 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
ld pw(ld n) { return n*n; }

const int MAXN = 1000005;

int X[MAXN], Y[MAXN];

ld Ans;
int N, L;

ld f(ld x) {
	ld ret = INFLL;
	for(int i = 1; i <= N; i++) {
		upmin(ret, sqrt(ld(pw(x-X[i]) + pw(Y[i]))));
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> L;
	for(int i = 1; i <= N; i++) cin >> X[i] >> Y[i];

	Ans = max(f(0), f(L));

	for(int i = 2; i <= N; i++) {
		int _s = max(0, X[i-1]), _e = min(L, X[i]);
		if(_s > _e) continue;

		ld s = _s, e = _e;
		for(int t = 0; t < 70; t++) {
			ld m1 = (s*2+e)/3, m2 = (s+e*2)/3;
			ld t1 = f(m1), t2 = f(m2);

			if(t1 < t2) s = m1;
			else e = m2;
		}

		upmax(Ans, f(s));
	}

	printf("%Lf\n", Ans);
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 444 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 3 ms 524 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 19 ms 604 KB Output is correct
3 Correct 17 ms 604 KB Output is correct
4 Correct 16 ms 684 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 1132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 1260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 1388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 1404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 1404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 4508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 5244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 5244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 6012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 6012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 6908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 6908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 8444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 8448 KB Time limit exceeded
2 Halted 0 ms 0 KB -