Submission #557511

#	Time	Username	Problem	Language	Result	Execution time	Memory
557511		aryan12	Mobile (BOI12_mobile)	C++17	100 / 100	886 ms	51112 KiB

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++)
	{
		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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5