This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define F first
#define S second
#define el '\n'
#define cout(x) for(auto v:x)cout<<v<<el
#define coutp(x) for(auto v:x)cout<<v.F<<' '<<v.S<<el
#define cin(x) for(auto &v:x)cin>>v;
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
const int N = 5e3 + 5, M = 1e2 + 5, Mod = 1e9 + 7;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int nxt()
{
int x;
cin >> x;
return x;
}
ld midX(pair<ld,ld> a, pair<ld,ld> b)
{
return (b.F * b.F + b.S * b.S - a.F * a.F - a.S * a.S) / (2 * b.F - 2 * a.F);
}
ld dist(pair<ld,ld> a, pair<ld,ld> b)
{
return sqrtl((a.F - b.F) * (a.F - b.F) + (a.S - b.S) * (a.S - b.S));
}
void solve(int h)
{
int n, m;
cin >> n >> m;
vector<pair<int,int>> v;
ld x[n], y[n];
deque<pair<ld,ld>> st;
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
x[i] = a;
y[i] = abs(b);
if (st.size() && st.back().F == x[i])
{
if (st.back().S <= y[i])
{
continue;
}
else
{
st.pop_back();
}
}
while (st.size() > 1 &&
midX(st[st.size() - 2], {x[i], y[i]}) <
midX(st.back(), {x[i], y[i]}))
{
st.pop_back();
}
st.push_back({x[i], y[i]});
}
while (st.size() > 2 &&
midX(st[0], st[1]) < 0)
{
st.pop_front();
}
while (st.size() > 2 &&
midX(st.back(), st[st.size() - 2]) > m)
{
st.pop_back();
}
ld mx = 0;
for (int i = 0; i < st.size(); i++)
{
pair<ld,ld> left = {0, 0}, right = {m, 0};
if (i)left.F = midX(st[i], st[i - 1]);
if (i != st.size() - 1)right.F = midX(st[i], st[i + 1]);
if (left.F < 0 || left.F > m || right.F < 0 || right.F > m)
continue;
mx = max({mx, dist(st[i], left), dist(st[i], right)});
}
cout << mx;
}
int32_t main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc = 1;
// cin >> tc;
for (int i = 1; i <= tc; i++)solve(i);
return 0;
}
Compilation message (stderr)
mobile.cpp: In function 'void solve(long long int)':
mobile.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < st.size(); i++)
| ~~^~~~~~~~~~~
mobile.cpp:83:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if (i != st.size() - 1)right.F = midX(st[i], st[i + 1]);
| ~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |