제출 #462077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
462077		shivensinha4	Mobile (BOI12_mobile)	C++17	100 / 100	779 ms	110704 KiB

mobile

#include <bits/stdc++.h>

#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<ll, 2> ii;
typedef pair<double, double> pdd;
#define endl '\n'

struct Line {
	mutable ll k, m, p;
	
	bool operator<(const Line &o) const { return k < o.k; }
	
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
	}
	
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

long double calc(Line &l, long double x) {
	return x*x - (l.k * x + l.m);
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	ll l;
	cin >> n >> l;
	vector <ii> pts(n);
	for_(i, 0, n) cin >> pts[i][0] >> pts[i][1];
	
	LineContainer lc;
	for_(i, 0, n) {
		lc.add(2 * pts[i][0], -pts[i][0] * pts[i][0] - pts[i][1] * pts[i][1]);
	}
	
	vector <Line> opt(lc.begin(), lc.end());
	long double ans = -lc.query(0);
	
	for_(i, 1, opt.size()) {
		long double num = (opt[i - 1].m - opt[i].m), den = (opt[i].k - opt[i - 1].k);
		long double intersect = num/den;
		if (intersect < 0 or intersect > l) continue;
		ans = max(ans, calc(opt[i-1], intersect));
//		cout << setprecision(10) << (intersect*intersect + -(opt[i-1].k * intersect + opt[i-1].m)) << endl;
//		cout << intersect << endl;
	}
	
	ans = max(ans, ((long double)l)*l - lc.query(l));
//	cout << ans << endl;
	cout << fixed << setprecision(8) << sqrtl(ans) << endl;
}

• 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