이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define inf 1000000007ll
#define llmax LLONG_MAX
#define pi 3.141592653589793238462643383279502884197169399
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
ll ncr(int n, int r)
{
if (n < r) return 0;
long long p = 1, k = 1;
if (n - r < r)
r = n - r;
if (r != 0) {
while (r) {
p *= n;
k *= r;
long long m = __gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else
p = 1;
return p;
}
vector <ll> vcreate(int n){
vector <ll> v(n);
for (int i = 0; i < n; i++)
{
cin>>v[i];
}
return v;
}
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
const int MOD=998244353;
ll ModExp(ll x, ll n, ll m) {
assert(n >= 0);
x %= m; // note: m * m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % m; }
x = x * x % m;
n /= 2;
}
return res;
}
long double dist(pair<long double,long double> x, pair<long double, long double> y)
{
return sqrtl((x.first-y.first)*(x.first-y.first) +(x.second-y.second)*(x.second-y.second));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
/* freopen("prime_subtractorization_input.txt", "r", stdin);
freopen("output.txt", "w", stdout); */
/* ll T;
cin>>T;
for(ll oo=0; oo<T; oo++)
{
} */
long double n{},l{};
cin>>n>>l;
vector<pair<long double,long double>> v(n);
for(int i{0}; i<n; i++)
{
cin>>v[i].first>>v[i].second;
}
vector<pair<long double,long double>> range(n,{0,l});
stack<int> st;
for(int i{0}; i<n; i++)
{
while(!st.empty())
{
pair<long double,long double> p;
p=v[st.top()];
long double cross=((p.first*p.first-v[i].first*v[i].first)+(p.second*p.second-v[i].second*v[i].second))/(2*p.first-2*v[i].first);
if(cross<=range[st.top()].first)
{
st.pop();
}
else
{
range[st.top()].second=cross;
range[i].first=cross;
break;
}
}
st.push(i);
}
/* for(int i{0}; i<n; i++)
{
cout<<range[i].first<<" "<<range[i].second<<endl;
} */
long double ans=0;
while(!st.empty())
{
long double d= dist(v[st.top()],{range[st.top()].first,0});
long double e=dist(v[st.top()],{range[st.top()].second,0});
ans=max(ans,d);
ans=max(ans,e);
st.pop();
}
cout<<ans<<endl;
}
# | 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... |