Submission #557506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
557506	2022-05-05T12:02:58 Z	aryan12	Mobile (BOI12_mobile)	C++17	50 / 100	1000 ms	45004 KB

mobile

#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 < 40)
	{
		// 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	31552 KB	Output is correct
2	Correct	27 ms	31640 KB	Output is correct
3	Correct	27 ms	31540 KB	Output is correct
4	Correct	27 ms	31556 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	31520 KB	Output is correct
2	Correct	26 ms	31564 KB	Output is correct
3	Correct	28 ms	31584 KB	Output is correct
4	Correct	27 ms	31576 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	31640 KB	Output is correct
2	Correct	31 ms	31592 KB	Output is correct
3	Correct	29 ms	31640 KB	Output is correct
4	Correct	28 ms	31700 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	31628 KB	Output is correct
2	Correct	30 ms	31708 KB	Output is correct
3	Correct	30 ms	31672 KB	Output is correct
4	Correct	35 ms	31668 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31564 KB	Output is correct
2	Correct	30 ms	31608 KB	Output is correct
3	Correct	30 ms	31668 KB	Output is correct
4	Correct	35 ms	31636 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	31704 KB	Output is correct
2	Correct	30 ms	31700 KB	Output is correct
3	Correct	31 ms	31680 KB	Output is correct
4	Correct	35 ms	31664 KB	Output is correct
5	Correct	34 ms	31648 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	31896 KB	Output is correct
2	Correct	82 ms	31832 KB	Output is correct
3	Correct	82 ms	31856 KB	Output is correct
4	Correct	178 ms	31896 KB	Output is correct
5	Correct	86 ms	31908 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	128 ms	31896 KB	Output is correct
2	Correct	131 ms	31880 KB	Output is correct
3	Correct	153 ms	31896 KB	Output is correct
4	Correct	166 ms	31896 KB	Output is correct
5	Correct	186 ms	31784 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	31856 KB	Output is correct
2	Correct	83 ms	31920 KB	Output is correct
3	Correct	105 ms	31896 KB	Output is correct
4	Correct	229 ms	31900 KB	Output is correct
5	Correct	145 ms	31856 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	31800 KB	Output is correct
2	Correct	96 ms	31780 KB	Output is correct
3	Correct	121 ms	31948 KB	Output is correct
4	Correct	230 ms	31852 KB	Output is correct
5	Correct	183 ms	31892 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	31988 KB	Output is correct
2	Correct	94 ms	31948 KB	Output is correct
3	Correct	113 ms	31900 KB	Output is correct
4	Correct	237 ms	32004 KB	Output is correct
5	Correct	187 ms	31948 KB	Output is correct

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	322 ms	31896 KB	Output is correct
2	Correct	382 ms	31900 KB	Output is correct
3	Correct	368 ms	31876 KB	Output is correct
4	Execution timed out	1035 ms	31892 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	380 ms	31900 KB	Output is correct
2	Correct	681 ms	31896 KB	Output is correct
3	Correct	460 ms	37412 KB	Output is correct
4	Execution timed out	1018 ms	40980 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	31892 KB	Output is correct
2	Correct	442 ms	31896 KB	Output is correct
3	Correct	437 ms	31896 KB	Output is correct
4	Execution timed out	1091 ms	31876 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	476 ms	31912 KB	Output is correct
2	Correct	816 ms	31896 KB	Output is correct
3	Correct	546 ms	38416 KB	Output is correct
4	Execution timed out	1028 ms	43304 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	460 ms	31888 KB	Output is correct
2	Correct	504 ms	31892 KB	Output is correct
3	Correct	503 ms	31820 KB	Output is correct
4	Execution timed out	1080 ms	31948 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	525 ms	31892 KB	Output is correct
2	Correct	972 ms	31948 KB	Output is correct
3	Correct	646 ms	40160 KB	Output is correct
4	Execution timed out	1082 ms	45004 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	512 ms	32012 KB	Output is correct
2	Correct	584 ms	31892 KB	Output is correct
3	Correct	585 ms	31852 KB	Output is correct
4	Execution timed out	1088 ms	31820 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	573 ms	31896 KB	Output is correct
2	Execution timed out	1078 ms	31888 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	633 ms	31964 KB	Output is correct
2	Correct	716 ms	31892 KB	Output is correct
3	Correct	740 ms	31892 KB	Output is correct
4	Execution timed out	1043 ms	31976 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	746 ms	31724 KB	Output is correct
2	Execution timed out	1088 ms	31760 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Submission #557506

Compilation message