Submission #754176

#	Time	Username	Problem	Language	Result	Execution time	Memory
754176		lukehsiao	Mobile (BOI12_mobile)	C++14	8 / 100	1071 ms	32344 KiB

mobile

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

const int mxN = 1e6;
ll n, L, x[mxN], y[mxN];

struct Range {
	double lo, hi;
	Range(double l, double r) : lo(l), hi(r) {};
	bool operator<(const Range &r) const {
		return hi < r.lo;
	}
	void merge(const Range &r) {
		lo = min(lo, r.lo);
		hi = max(hi, r.hi);
	}
};

bool works(double r) {
	set<Range> s;
	for (int i=0; i<n; ++i) {
		double d = r*r - y[i]*y[i];
		if (d >= 0) {
			Range rng = Range(x[i]-sqrt(d), x[i]+sqrt(d));
			auto it1 = s.lower_bound(rng);
			auto it2 = s.upper_bound(rng);
			while (it1 != it2) {
				rng.merge(*it1);
				it1 = s.erase(it1);
			}
			s.insert(rng);
		}
	}
	for (const Range &rng : s)
		if (rng.lo <= 0 && rng.hi >= L)
			return true;
	return false;
}

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

	cin >> n >> L;
	for (int i=0; i<n; ++i)
		cin >> x[i] >> y[i];
	
	double lo = 0, hi = 3e9;
	while (hi-lo > 1e-3) {
		double mid = (lo+hi)/2;
		if (works(mid))
			hi = mid;
		else
			lo = mid;
	}

	cout << (lo+hi)/2 << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 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