Submission #1229661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229661		atillama	Mobile (BOI12_mobile)	C++20	0 / 100	1098 ms	65308 KiB

mobile

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;

#define int long long
#define double long double
#define pb push_back
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cout << #x << " = " << x << '\n';
#define vdebug(a) cout << #a << " = "; for(auto x : a) cout << x << " "; cout << '\n';

const double eps = 1e-9;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int INF = 1e18;

signed main(){
    fastio;
	int n, l;
	cin >> n >> l;
	vector<pair<int, int>> v;
	for(int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		v.pb({x, y});
	}
	double best = INF;
	double lo = 0;
	double hi = l;
	while(hi - lo > 1e-4){
		double mid = (hi + lo) / 2.0;
		vector<pair<double, double>> lr; // l, r
		for(int i = 0; i < n; i++){
			int x = v[i].first;
			int y = v[i].second;
			// a*a + b*b = c*c
			// a*a + y*y = mid*mid
			double a = sqrtl(mid * mid - y * y);
			lr.pb({x - a, x + a});
		}
		sort(lr.begin(), lr.end());
		bool b = true;
		if(lr[0].first > 0){
			b = false;
		}
		double mxr = lr[0].second;
		for(int i = 1; i < lr.size(); i++){
			mxr = max(mxr, lr[i - 1].second);
			if(lr[i].first > mxr){
				b = false;
				break;
			}
		}
		if(b){
			best = mid;
			hi = mid;
		}else{
			lo = mid;
		}
	}
	cout << best << '\n';
}

/*
    freopen("x.in", "r", stdin);
    freopen("x.out", "w", stdout);
*/

//atilla

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5