oj.uz

답안 #557505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557505 2022-05-05T12:01:59 Z aryan12 Mobile (BOI12_mobile) C++17
50 / 100
 1000 ms 48132 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());


const int N = 1e6 + 5;
vector<pair<long double, long double> > coordinates(N);
int n, l;


bool Check(long double value)
{

	// sqrt[(c[i].x - x) ^ 2 + (c[i].y - 0) ^ 2] = value
	// (c[i].x - x) ^ 2 + c[i].y ^ 2 = value * value
	// c[i].x - x = sqrt[(value * value) - c[i].y ^ 2]
	// - x = sqrt[(value * value) - c[i].y ^ 2] - c[i].x
	// x = c[i].x - sqrt[(value * value) - c[i].y ^ 2]

	long double maxLeft = 0;
	for(int i = 1; i <= n; i++)
	{
		long double cur_left = 0.0, cur_right = 0.0;
		cur_left = coordinates[i].first - sqrt((value * value) - (coordinates[i].second * coordinates[i].second));
		cur_right = coordinates[i].first + sqrt((value * value) - (coordinates[i].second * coordinates[i].second));
		if(cur_left <= maxLeft)
		{
			maxLeft = max(maxLeft, cur_right);
		}
	}
	return (maxLeft >= l);
}


void Solve() 
{
	cin >> n >> l;
	for(int i = 1; i <= n; i++)
	{
		cin >> coordinates[i].first >> coordinates[i].second;
	}
	long double left = 0, right = 1e9;
	long double ans = right + 1;
	int cnt = 0;
	while(cnt < 60)
	{
		// cout << "left = " << left << ", right = " << right << "\n";
		cnt++;
		long double mid = (left + right) / 2;
		if(Check(mid))
		{
			right = mid;
			ans = mid;
		}
		else
		{
			left = mid;
		}
	}
	cout << fixed << setprecision(8) << ans << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31572 KB Output is correct
2 Correct 26 ms 31648 KB Output is correct
3 Correct 25 ms 31564 KB Output is correct
4 Correct 26 ms 31616 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 31644 KB Output is correct
2 Correct 27 ms 31552 KB Output is correct
3 Correct 26 ms 31644 KB Output is correct
4 Correct 27 ms 31548 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 31564 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 30 ms 31588 KB Output is correct
4 Correct 27 ms 31640 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 31656 KB Output is correct
2 Correct 32 ms 31648 KB Output is correct
3 Correct 31 ms 31700 KB Output is correct
4 Correct 38 ms 31668 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 31652 KB Output is correct
2 Correct 30 ms 31660 KB Output is correct
3 Correct 31 ms 31572 KB Output is correct
4 Correct 36 ms 31700 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 31680 KB Output is correct
2 Correct 32 ms 31712 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 37 ms 31700 KB Output is correct
5 Correct 35 ms 31576 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 32428 KB Output is correct
2 Correct 94 ms 32648 KB Output is correct
3 Correct 88 ms 32140 KB Output is correct
4 Correct 214 ms 32736 KB Output is correct
5 Correct 125 ms 32028 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 32488 KB Output is correct
2 Correct 190 ms 32448 KB Output is correct
3 Correct 212 ms 32664 KB Output is correct
4 Correct 228 ms 32860 KB Output is correct
5 Correct 253 ms 33032 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 32328 KB Output is correct
2 Correct 91 ms 32716 KB Output is correct
3 Correct 134 ms 32668 KB Output is correct
4 Correct 309 ms 33484 KB Output is correct
5 Correct 215 ms 32568 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 33100 KB Output is correct
2 Correct 105 ms 33036 KB Output is correct
3 Correct 141 ms 32664 KB Output is correct
4 Correct 311 ms 33672 KB Output is correct
5 Correct 259 ms 32772 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 33164 KB Output is correct
2 Correct 104 ms 33052 KB Output is correct
3 Correct 152 ms 32676 KB Output is correct
4 Correct 303 ms 33568 KB Output is correct
5 Correct 257 ms 32912 KB Output is correct

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 35940 KB Output is correct
2 Correct 428 ms 39372 KB Output is correct
3 Correct 438 ms 38800 KB Output is correct
4 Execution timed out 1073 ms 41232 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 39888 KB Output is correct
2 Execution timed out 1014 ms 38292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 492 ms 36820 KB Output is correct
2 Correct 525 ms 41036 KB Output is correct
3 Correct 507 ms 40344 KB Output is correct
4 Execution timed out 1076 ms 43544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 569 ms 41516 KB Output is correct
2 Execution timed out 1090 ms 39500 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 550 ms 37696 KB Output is correct
2 Correct 591 ms 42448 KB Output is correct
3 Correct 596 ms 41752 KB Output is correct
4 Execution timed out 1065 ms 45080 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 43188 KB Output is correct
2 Execution timed out 1083 ms 40872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 625 ms 38536 KB Output is correct
2 Correct 659 ms 44032 KB Output is correct
3 Correct 670 ms 43276 KB Output is correct
4 Execution timed out 1036 ms 47368 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 703 ms 44824 KB Output is correct
2 Execution timed out 1094 ms 42188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 768 ms 40460 KB Output is correct
2 Correct 852 ms 47200 KB Output is correct
3 Correct 818 ms 46192 KB Output is correct
4 Execution timed out 1056 ms 47520 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 837 ms 48132 KB Output is correct
2 Execution timed out 1069 ms 44860 KB Time limit exceeded
3 Halted 0 ms 0 KB -