Submission #1131277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131277		lucaskojima	Mobile (BOI12_mobile)	C++17	0 / 100	1098 ms	48168 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;
const int EPS = 1e-3;

struct point {
	double x, y;
	bool operator<(const point &o) { return x < o.x; }
};

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 {
		vector<point> aux;
		for (int i = 0; i < n; i++) {
			double dd = sqrt(d * d - v[i].y * v[i].y);
			aux.push_back({v[i].x - dd, v[i].x + dd});
		}

		sort(all(aux));

		double p = 0;
		for (int i = 0; i < n; i++) {
			if (p < aux[i].x) return false;
			p = max(p, aux[i].y);
			if (p > k) return true;
		}
		return p > k;
	};

	double l = 0; 	// l is bad
	double r = 1e9; // r is good
	for (int i = 0; i < 100; i++) {
		double m = (l + r) / 2;
		check(m) ? r = m : l = m;
	}

	cout << fixed << setprecision(6) << r << nl;
	return 0;
}

• 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