Submission #1100856

#TimeUsernameProblemLanguageResultExecution timeMemory
1100856sanoMobile (BOI12_mobile)C++14
100 / 100
416 ms71088 KiB
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short double
#define pii pair<long double, long double>
#define NEK 2147483640
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8

using namespace std;

long double bod(pii a, pii b) {
	return (b.first * b.first + b.second * b.second - a.first * a.first - a.second * a.second) / (2 * (b.first - a.first));
}

long double dist(pii a, pii b) {
	return sqrt(abs(a.ff - b.ff) * abs(a.ff - b.ff) + abs(a.ss - b.ss) * (abs(a.ss - b.ss)));
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	long double n, l;
	cin >> n >> l;
	vec<pii> p;
	vec<long double> s;
	For(i, n) {
		long double x, y;
		cin >> x >> y;
		y = abs(y);
		if (!p.empty()) {
			if (p.back().ff == x) {
				if (p.back().ss > y) {
					p.pop_back();
					p.push_back({ x, y });
				}
				continue;
			}
		}
		p.push_back({ x, y });
	}
	For(i, p.size()) {
		while (s.size() > 1 && bod(p[s[s.size() - 2]], p[s.back()]) > bod(p[s.back()], p[i])) s.pop_back();
		s.push_back(i);
	}
	while (s.size() > 1 && bod(p[s[s.size() - 2]], p[s.back()]) > l) s.pop_back();
	long double md = 0; bool prvy = false;
	For(i, (s.size() - 1)) {
		long double hod = bod(p[s[i]], p[s[i + 1]]);
		if (hod < 0) continue;
		if (prvy == false) {
			md = dist(p[s[i]], { 0, 0 });
			prvy = true;
		}
		md = max(md, dist(p[s[i]], { hod, 0 }));
		md = max(md, dist(p[s[i + 1]], { hod, 0 }));
	}
	md = max(md, dist(p[s.back()], { l, 0 }));
	cout << fixed << setprecision(3);
	cout << md << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...