Submission #684604

#	Time	Username	Problem	Language	Result	Execution time	Memory
684604		aaggupta07	Mobile (BOI12_mobile)	C++17	0 / 100	1097 ms	15956 KiB

mobile

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
#define f first
#define s second
#define mp make_pair

constexpr int MAX_C = 1.5e9;
constexpr int MAX_N = 1e6;
constexpr double tol = 0.00000001L;

using pi = pair<int, int>;
using pd = pair<double, double>;

int n, l;
pi towers[MAX_N];

bool doubleEq(double a, double b) {
	return abs(a - b) <= tol;
}

double calcDist(int i, double d) {
	return sqrt((d * d) - (towers[i].s * towers[i].s));
}

bool check(double p) {
	// cout << "Called: " << p << endl;

	double best = 0;
	for(int i = 0; i < n; ++i) {
		if(abs(towers[i].s) >= p || doubleEq(abs(towers[i].s), p)) continue;

		double dist = calcDist(towers[i].s, p), d1 = towers[i].f - dist, d2 = towers[i].f + dist;
		// if(p - 6.98 <= 0.1) cout << d1 << ' ' << d2 << endl;

		if(d1 < best || doubleEq(d1, best)) best = max(best, d2);
	}

	// if(p - 6.98 <= 0.1) {
	// 	cout << "------------------" << endl;
	// 	cout << start << ' ' << curEnd << '\n';
	// 	// for(int i = 0; i < n; ++i) cout << intervals[i].f << ' ' << intervals[i].s << endl;
	// 	cout << "------------------" << endl;
	// }

	if(best > l || doubleEq(best, l)) return true;
	return false;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> l;
	for(int i = 0; i < n; ++i) cin >> towers[i].f >> towers[i].s;
	
	double le = 0, r = MAX_C;
	while(r - le >= 1e-3) {
		double mid = (le + r) / 2;
		if(check(mid)) r = mid;
		else le = mid;
	}
	
	cout.precision(4);
	cout << fixed << le << '\n';
}

• 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