oj.uz

답안 #670686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670686 2022-12-09T20:51:40 Z thiago_bastos Mobile (BOI12_mobile) C++17
100 / 100
 439 ms 23624 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 1e6 + 10;
int n, l;
ii pt[N];

bool evaluate(double d) {
	double last = 0;
	for(int i = 0; i < n; ++i) {
		auto [x, y] = pt[i];
		if(abs(y) > d) continue;
		double z = sqrt(d * d - (i64)y * y);
		if(max(0.0, x - z) <= last) last = max(last, min(l + 0.0, x + z));
	}
	return last >= l;
}

void solve() {
	cin >> n >> l;
	for(int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		pt[i] = {x, y};
	}
	sort(pt, pt + n);
	double lo = 0, hi = 2 * INF;	
	for(int i = 0; i < 45; ++i) {
		double m = (lo + hi) / 2;
		if(evaluate(m)) hi = m;
		else lo = m;
	}
	cout << fixed << setprecision(9) << hi << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 400 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 344 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 852 KB Output is correct
2 Correct 26 ms 852 KB Output is correct
3 Correct 17 ms 1284 KB Output is correct
4 Correct 22 ms 2040 KB Output is correct
5 Correct 14 ms 1040 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 940 KB Output is correct
2 Correct 20 ms 756 KB Output is correct
3 Correct 23 ms 964 KB Output is correct
4 Correct 22 ms 836 KB Output is correct
5 Correct 33 ms 988 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 980 KB Output is correct
2 Correct 28 ms 940 KB Output is correct
3 Correct 27 ms 1852 KB Output is correct
4 Correct 30 ms 3036 KB Output is correct
5 Correct 26 ms 1928 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 1108 KB Output is correct
2 Correct 35 ms 2380 KB Output is correct
3 Correct 32 ms 2116 KB Output is correct
4 Correct 30 ms 2996 KB Output is correct
5 Correct 31 ms 2324 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 1032 KB Output is correct
2 Correct 36 ms 1092 KB Output is correct
3 Correct 31 ms 2000 KB Output is correct
4 Correct 29 ms 2928 KB Output is correct
5 Correct 32 ms 2260 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 4216 KB Output is correct
2 Correct 177 ms 11892 KB Output is correct
3 Correct 185 ms 11432 KB Output is correct
4 Correct 154 ms 13748 KB Output is correct
5 Correct 147 ms 11112 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 4216 KB Output is correct
2 Correct 227 ms 10816 KB Output is correct
3 Correct 149 ms 9872 KB Output is correct
4 Correct 142 ms 13516 KB Output is correct
5 Correct 144 ms 11396 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 5036 KB Output is correct
2 Correct 211 ms 14244 KB Output is correct
3 Correct 213 ms 13700 KB Output is correct
4 Correct 177 ms 16948 KB Output is correct
5 Correct 171 ms 12876 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 5012 KB Output is correct
2 Correct 278 ms 12928 KB Output is correct
3 Correct 186 ms 11748 KB Output is correct
4 Correct 176 ms 16724 KB Output is correct
5 Correct 183 ms 13700 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 5744 KB Output is correct
2 Correct 248 ms 16616 KB Output is correct
3 Correct 255 ms 15820 KB Output is correct
4 Correct 199 ms 19240 KB Output is correct
5 Correct 198 ms 14744 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 5784 KB Output is correct
2 Correct 299 ms 15024 KB Output is correct
3 Correct 216 ms 14156 KB Output is correct
4 Correct 208 ms 19192 KB Output is correct
5 Correct 196 ms 15864 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 6732 KB Output is correct
2 Correct 287 ms 19024 KB Output is correct
3 Correct 294 ms 18184 KB Output is correct
4 Correct 235 ms 22240 KB Output is correct
5 Correct 230 ms 17616 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 6800 KB Output is correct
2 Correct 342 ms 17100 KB Output is correct
3 Correct 256 ms 16192 KB Output is correct
4 Correct 241 ms 22016 KB Output is correct
5 Correct 223 ms 18096 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 8324 KB Output is correct
2 Correct 362 ms 23624 KB Output is correct
3 Correct 357 ms 22592 KB Output is correct
4 Correct 281 ms 8652 KB Output is correct
5 Correct 293 ms 21780 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 8136 KB Output is correct
2 Correct 439 ms 21284 KB Output is correct
3 Correct 326 ms 20372 KB Output is correct
4 Correct 279 ms 8652 KB Output is correct
5 Correct 293 ms 22856 KB Output is correct