oj.uz

Submission #557511

# Submission time Handle Problem Language Result Execution time Memory
557511 2022-05-05T12:09:24 Z aryan12 Mobile (BOI12_mobile) C++17
100 / 100
 886 ms 51112 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++)
	{
		if(value * value - coordinates[i].second * coordinates[i].second <= 0.000001)
		{
			continue;
		}
		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 >= (long double)(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;
	while(right - left >= 0.0001)
	{
		// cout << "left = " << left << ", right = " << right << "\n";
		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

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31644 KB Output is correct
2 Correct 30 ms 31572 KB Output is correct
3 Correct 28 ms 31636 KB Output is correct
4 Correct 27 ms 31532 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31720 KB Output is correct
2 Correct 26 ms 31564 KB Output is correct
3 Correct 26 ms 31820 KB Output is correct
4 Correct 28 ms 31560 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31656 KB Output is correct
2 Correct 28 ms 31584 KB Output is correct
3 Correct 30 ms 31556 KB Output is correct
4 Correct 35 ms 31564 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31696 KB Output is correct
2 Correct 29 ms 31836 KB Output is correct
3 Correct 30 ms 31680 KB Output is correct
4 Correct 29 ms 31692 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31632 KB Output is correct
2 Correct 31 ms 31692 KB Output is correct
3 Correct 32 ms 31676 KB Output is correct
4 Correct 33 ms 31656 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31700 KB Output is correct
2 Correct 29 ms 31724 KB Output is correct
3 Correct 29 ms 31672 KB Output is correct
4 Correct 31 ms 31652 KB Output is correct
5 Correct 29 ms 31612 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 31900 KB Output is correct
2 Correct 79 ms 31880 KB Output is correct
3 Correct 67 ms 31972 KB Output is correct
4 Correct 75 ms 31828 KB Output is correct
5 Correct 64 ms 31900 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 31900 KB Output is correct
2 Correct 72 ms 31892 KB Output is correct
3 Correct 88 ms 31892 KB Output is correct
4 Correct 78 ms 31832 KB Output is correct
5 Correct 82 ms 31820 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 31868 KB Output is correct
2 Correct 95 ms 31896 KB Output is correct
3 Correct 85 ms 31896 KB Output is correct
4 Correct 97 ms 31896 KB Output is correct
5 Correct 82 ms 31808 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 31780 KB Output is correct
2 Correct 99 ms 31840 KB Output is correct
3 Correct 94 ms 31932 KB Output is correct
4 Correct 100 ms 31800 KB Output is correct
5 Correct 95 ms 31860 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 31904 KB Output is correct
2 Correct 99 ms 31896 KB Output is correct
3 Correct 101 ms 31896 KB Output is correct
4 Correct 118 ms 32020 KB Output is correct
5 Correct 93 ms 31872 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 31896 KB Output is correct
2 Correct 398 ms 31896 KB Output is correct
3 Correct 398 ms 31896 KB Output is correct
4 Correct 378 ms 31896 KB Output is correct
5 Correct 389 ms 38424 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 31948 KB Output is correct
2 Correct 457 ms 31896 KB Output is correct
3 Correct 406 ms 31692 KB Output is correct
4 Correct 375 ms 31768 KB Output is correct
5 Correct 366 ms 38924 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 32008 KB Output is correct
2 Correct 486 ms 31896 KB Output is correct
3 Correct 498 ms 31960 KB Output is correct
4 Correct 444 ms 31956 KB Output is correct
5 Correct 429 ms 39572 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 31896 KB Output is correct
2 Correct 514 ms 31888 KB Output is correct
3 Correct 407 ms 31768 KB Output is correct
4 Correct 457 ms 31804 KB Output is correct
5 Correct 447 ms 40372 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 31896 KB Output is correct
2 Correct 540 ms 31896 KB Output is correct
3 Correct 609 ms 31820 KB Output is correct
4 Correct 516 ms 31896 KB Output is correct
5 Correct 510 ms 40596 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 31896 KB Output is correct
2 Correct 591 ms 31892 KB Output is correct
3 Correct 487 ms 31908 KB Output is correct
4 Correct 557 ms 31892 KB Output is correct
5 Correct 498 ms 41744 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 31888 KB Output is correct
2 Correct 594 ms 31896 KB Output is correct
3 Correct 645 ms 31892 KB Output is correct
4 Correct 603 ms 31892 KB Output is correct
5 Correct 559 ms 42816 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 31896 KB Output is correct
2 Correct 680 ms 32008 KB Output is correct
3 Correct 577 ms 41176 KB Output is correct
4 Correct 619 ms 47128 KB Output is correct
5 Correct 585 ms 43236 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 31892 KB Output is correct
2 Correct 767 ms 31812 KB Output is correct
3 Correct 732 ms 31904 KB Output is correct
4 Correct 755 ms 32012 KB Output is correct
5 Correct 697 ms 45340 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 31652 KB Output is correct
2 Correct 886 ms 31896 KB Output is correct
3 Correct 712 ms 44052 KB Output is correct
4 Correct 788 ms 51112 KB Output is correct
5 Correct 683 ms 46380 KB Output is correct