Submission #1255668

#TimeUsernameProblemLanguageResultExecution timeMemory
1255668settopMobile (BOI12_mobile)C++20
0 / 100
101 ms16200 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 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=4e2+10; const int MAXL=5e2+10; const int inf=1e17; const int MOD=1e9+7; typedef pair<int,int> 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,last[MAXN]; 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; last[0]=-1; fall(i,1,n-1){ int p=i-1; while(p!=-1){ if(r[p]==-1) p=last[p]; else if(sq(l[p]-v[p].F)+sq(v[p].S)>sq(l[p]-v[i].F)+sq(v[p].S)){ l[i]=l[p],r[i]=k; l[p]=r[p]=-1; p=last[p]; } else{ double ini=l[p],fim=k,ans=-1; fall(_,1,40){ double mei=(ini+fim)/2.00; if(sq(mei-v[p].S)+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; last[i]=p; } break; } } } 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...