제출 #1255679

#제출 시각아이디문제언어결과실행 시간메모리
1255679settopMobile (BOI12_mobile)C++20
100 / 100
508 ms71192 KiB
#include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define double long double #define int long long #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> #define eb emplace_back #define S second #define dbg(v) cerr << #v << " = " << v << "\n" #define F first #define fall(i,a,n) for(int i=a;i<=n;i++) #define rfall(i,a,n) for(int i=a;i>=n;i--) #define pb push_back #define all(x) x.begin(),x.end() #define lsb(x) (x & -x) #define sz(x) (int)x.size() const int MAXN=1e6+10; const int MAXL=5e2+10; const int inf=1e17; const int MOD=1e9+7; typedef pair<double,double> pii; typedef tuple<int,int,int> trio; typedef tuple<int,int,int,int> squad; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,k; double l[MAXN],r[MAXN]; vector<pii> v; double sq(double x){ return x*x; } int32_t main(){ std::ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen("cowrun.in","r",stdin); //freopen("cowrun.out","w",stdout); cin>>n>>k; v.resize(n); for(auto &[u,j]:v) cin>>u>>j; l[0]=0,r[0]=k; stack<int> st; st.push(0); fall(i,1,n-1){ while(!st.empty()){ auto p=st.top(); if(sq(l[p]-v[p].F)+sq(v[p].S)>sq(l[p]-v[i].F)+sq(v[i].S)){ l[i]=l[p],r[i]=k; l[p]=r[p]=-1; st.pop(); } else{ double ini=l[p],fim=k,ans=-1; while(fim-ini>1e-6){ double mei=(ini+fim)/2.00; if(sq(mei-v[p].F)+sq(v[p].S)>sq(mei-v[i].F)+sq(v[i].S)) ans=mei,fim=mei; else ini=mei; } if(ans==-1) l[i]=r[i]=-1; else{ l[i]=ans; r[i]=k; r[p]=ans; } break; } } if(r[i]!=-1) st.push(i); } double ans=0; fall(i,0,n-1){ if(r[i]==-1) continue; ans=max(ans,sqrt(sq(l[i]-v[i].F)+sq(v[i].S))); ans=max(ans,sqrt(sq(r[i]-v[i].F)+sq(v[i].S))); } cout.precision(6); cout.setf(ios::fixed); cout<<ans<<"\n"; }
#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...