Submission #1229754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229754		atillama	Mobile (BOI12_mobile)	C++17	100 / 100	381 ms	16996 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 = 1e10;
	while(hi - lo > 1e-7){
		double mid = (hi + lo) / 2.0;
		double mx = 0;
		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
			if(mid * mid < y * y){
				continue;
			}
			double a = sqrtl(mid * mid - y * y);
			if(x - a <= mx){
				mx = max(mx, x + a);
			}
		}
		if(mx >= l){
			best = mid;
			hi = mid;
		}else{
			lo = mid;
		}
	}
  cout << fixed << setprecision(6) << best << '\n';
}

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

//atilla

• 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