Submission #1079314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079314		EmmaXII	Mobile (BOI12_mobile)	C++17	31 / 100	1059 ms	64772 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;
	double L;
	cin >> N >> L;

	vector<double> X(N);
	vector<double> 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) return -1.0;
		return sqrt(r*r - y*y);
	};

	auto can_do = [&](double R) {
		vector<pair<double, double>> ivals;
		for (int i=0;i<N;i++) {
			double hw = get_hw(Y[i], R);
			if (hw < 0) continue;
			ivals.push_back({X[i] - hw, X[i] + hw});
		}
		sort(all(ivals));
		double progress = 0.;
		for (auto [l, r] : ivals) {
			if (l > progress) return false;
			progress = max(progress, r);
		}

		return progress >= L;
	};

	double lo = 0;
	double hi = L + abs(X[0]) + abs(Y[0]);

	while (hi - lo > 1e-4) {
		double mid = (lo + hi) / 2;
		if (can_do(mid)) hi = mid;
		else lo = mid;
	}
	cout << setprecision(10);
	cout << lo << endl;

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 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