Submission #1131280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131280		lucaskojima	Mobile (BOI12_mobile)	C++17	100 / 100	542 ms	15944 KiB

mobile

#include "bits/stdc++.h"
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

struct point {
	double x, y;
};

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int n; double k; cin >> n >> k;
	vector<point> v(n); for (auto &[a, b] : v) cin >> a >> b;

	auto check = [&](double d) -> bool {
		double p = 0;
		for (int i = 0; i < n; i++) {
			double dd = sqrt(d * d - v[i].y * v[i].y);
			double l = v[i].x - dd, r = v[i].x + dd;
			if (l <= p) p = max(p, r);
		}
		return p >= k;
	};

	double l = 0;  	// l is bad
	double r = 1e9; // r is good
	while (r - l > 1e-3) {
		double m = (l + r) / 2;
		check(m) ? r = m : l = m;
	}

	cout << fixed << setprecision(6) << r << nl;
	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