Submission #1092980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092980		TommasoUlian	Mobile (BOI12_mobile)	C++17	100 / 100	296 ms	35436 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
 
#define all(x) x.begin(), x.end()
 
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int N;
	ll L;
	cin >> N >> L;
 
	vector<ll> X(N);
	vector<ll> Y(N);
	for (int i=0;i<N;i++) cin >> X[i] >> Y[i];
 
	auto get_hw = [&](double y, double r) {
		if (abs(y) > r - 1e-6) return -1.0;
		return sqrt((r-y) * (r+y));
	};
 
	auto can_do = [&](double R) {
		double progress = 0.;
		for (int i=0;i<N;i++) {
			double hw = get_hw((double)Y[i], R);
			if (hw < 0) continue;
 
			double l = (double)X[i] - hw;
			double r = (double)X[i] + hw;
			if (l <= progress + 1e-6) progress = max(progress, r);
			if (progress >= (double)L) return true;
		}
 
		return false;
	};
 
	double lo = 1;
	double hi = 2e9;
 
	while (hi - lo > 1e-4) {
		double mid = (lo + hi) / 2;
		if (can_do(mid)) hi = mid;
		else lo = mid;
	}
	cout << setprecision(18);
	cout << (lo + hi)/2 << endl;
 
	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