Submission #1129375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129375		yazansh	Balloons (CEOI11_bal)	C++20	100 / 100	154 ms	8080 KiB

bal

/*
the author :
 Luffy-san 
"yazan sharba" 
*/
#include <bits/stdc++.h> 
using namespace std; 
 /*
 ⠀⠀⠀⠀⠀⠀⠀⠙⢦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡠⠒⠁⠀⠀⠀⠀⠀⠘⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠓⠤⠤⠤⠤⠄⠒⠒⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠶⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢷⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡴⠟⠉⠀⠙⢿⣷⣦⣤⣀⣀⣀⡀⠄
⠀⠀⠙⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠿⢶⣤⣄⣀⡀⠀⠀⠀⣀⣀⣤⣤⡶⠟⠋⠀⠀⠀⠀⠀⠘⢿⣿⣿⠁⠀⠀⠀⠀
⠀⠀⠀⠀⢲⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣾⠃⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠻⣿⣶⣶⣿⡿⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⡇⠀⠀⠀⠀
⠳⡄⠀⠀⣸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣤⣤⣷⣾⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⡿⠋⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡇⠀⠀⠀⠀
⠀⢹⡀⢠⡟⠀⠀⠀⠀⠀⢀⣴⠀⠀⠀⠀⠀⢀⣴⡿⠋⠉⠹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⣾⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣷⠀⠀⠀⠀
⠀⢠⣿⡟⠀⠀⠀⠀⠰⣴⡿⠃⠀⠀⠀⠀⢠⣾⣿⣧⡀⠀⠀⣿⠁⠀⠀⠀⠀⠀⠀⢀⣠⣶⡟⣫⡽⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢾⣧⠀⠀⠀
⣶⣿⡟⠀⠀⠀⠀⠀⣼⣿⠃⠀⠀⠀⠀⢠⣿⣿⢃⣿⣷⣄⢸⡟⠀⠀⠀⠀⠀⠀⣰⣿⣿⠿⠿⠿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣦⣿⡆⠀⠀
⠻⣿⠀⠀⠀⠀⠀⣼⣿⣿⠀⠀⠀⠀⣠⣾⣿⠿⠋⠁⠈⣻⣾⣧⠀⠀⠀⠀⢀⣾⣿⡟⠁⣀⠀⠀⠀⠹⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠿⠛⣿⡀⠀
⣶⣿⣦⣀⣀⣤⣾⣿⡟⢿⣇⡀⠀⢀⣿⣿⠋⠀⣠⣾⠟⣿⣿⣿⡀⠀⠀⠀⣸⡟⢻⡆⠈⢻⣿⠀⠀⢠⡿⠀⢰⡇⠀⠀⠀⠀⢀⣤⠶⢶⣄⠀⠀⠀⠀⠀⣠⡴⠟⠁⠀⠀⣿⡇⠀
⣿⠁⠉⠻⣿⣿⣿⡏⠁⠘⢿⣷⣶⣿⡿⠃⠀⠀⣿⣁⣶⣿⣿⣿⣇⡀⠀⣀⣿⣅⠈⠛⠷⠛⠁⠀⢀⣾⠇⢠⡾⠀⠀⠀⣠⡶⠋⠁⠀⠀⠹⣧⠀⢀⣴⠾⠋⠀⠀⢀⣤⣾⣿⡇⠀
⢿⡇⠀⠀⢻⣿⠇⠀⠀⠀⠈⣿⠟⠻⣇⠀⠀⠀⢿⣏⠻⣿⠏⢉⣿⣿⠿⠿⠿⢿⣦⣀⠀⣀⣠⣴⡿⢋⣴⠟⠁⠀⠀⣴⠟⠀⢠⣤⠀⠀⣰⣿⠿⠋⠁⠀⢀⣠⣴⡿⠟⢉⣿⡇⠀
⠈⠿⣶⣤⣼⣿⠀⠀⠀⠀⠀⠀⠀⠀⢻⣆⠀⠀⠈⢿⣿⣿⣾⠿⠛⠁⠀⠀⠀⢸⣿⣿⢿⣟⠿⠛⠛⠛⠁⠀⠀⠀⣸⣿⠀⠀⠙⢷⣶⠟⠋⠀⠀⣀⣤⣾⣿⡟⠁⠀⢺⣾⡿⠀⠀
⠉⠀⠈⠉⠃⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠛⢻⣎⣿⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣷⣤⣤⣤⣤⣴⣶⣾⣿⡋⠁⠀⢻⡇⠀⠀⣼⡟⠁⠀⠀
⣦⠀⠀⠀⠀⣿⡀⠀⠀⠀⠀⠀⣶⡀⠀⠀⠀⠙⠛⠶⣤⣄⣀⣀⣠⣤⡴⠾⠛⠁⠀⠈⠉⠙⠀⠀⠀⠀⠀⢠⣿⠟⠉⣿⠋⢹⣿⣏⣴⣿⣷⠞⣻⡟⠀⠀⢸⣷⣠⣼⠏⠀⠀⠀⠀
⢿⣿⣦⣤⣀⣿⡇⠀⠀⠀⢀⣴⠿⣷⣄⠀⠀⠀⠀⠀⠀⠈⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠀⠀⣿⠀⠘⢿⣭⣛⣛⣛⣴⡿⠁⠀⠀⣸⣿⣿⠃⠀⠀⠀⠀⠀
⠀⠙⠻⣿⣿⣿⣧⠀⠀⠀⣸⡏⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⣿⠁⠀⠀⠹⣧⡀⠀⠉⠙⠛⠉⠁⠀⠀⣠⡾⠛⠛⣿⠀⠀⠀⠀⣠⡟
⠀⠀⠀⠀⠙⠿⣿⣷⡀⠀⣿⠁⠀⠀⠀⠈⢿⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡟⠀⣿⠀⠀⠀⠀⠈⠛⠶⠶⢤⡶⠶⠶⠿⠛⠁⠀⠀⠀⣿⣷⡶⠞⡩⠛⠀
⠀⠀⠀⠀⠀⠀⠘⠻⢿⣄⣿⡀⠀⠀⠀⢰⠟⠈⠙⠿⣷⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀⣃⣰⣿⠀⠀⢀⣤⣀⠀⠀⠀⠀⡀⠀⣀⣶⠶⠛⠀⠀⣼⣿⣿⠿⠋⢀⣠⠆
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣧⡀⠀⢀⡟⠀⠀⠀⠀⠈⠙⠻⢷⣦⣄⡀⠀⠀⠀⠀⠀⠀⠙⣷⣄⣴⣿⡿⠋⠀⠀⠀⠈⠙⠛⠛⠒⠲⣿⠛⠉⠁⠀⠀⢀⣾⠋⠉⠀⣀⣴⣿⡟⠃
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⣷⡄⣾⠁⠀⠀⠀⠀⠀⠀⢀⡾⠉⠙⠛⠿⣶⣦⣄⣀⠀⠀⠈⠛⠛⠡⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣿⠀⠀⠀⠀⣰⣿⣃⣤⣶⠾⠛⠉⠁⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣿⡄⠀⠀⠀⠀⠀⠀⡾⠀⠀⠀⠀⠀⠀⠈⢹⡟⠻⠷⠶⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣴⠟⠁⠀⠀⢀⣼⣿⣿⠟⠉⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⠿⣶⣄⠀⠀⠀⡼⠁⠀⠀⠀⠀⠀⠀⢀⡾⠁⠀⠀⠀⠀⣸⠋⠉⠈⠉⠉⣿⠉⠀⣠⠞⠁⠀⠀⠀⣀⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠙⠻⣦⣴⡃⠀⠀⠀⠀⠀⠀⢀⡾⠁⠀⠀⠀⠀⢰⡟⠀⠀⠀⠀⣸⢇⣠⠾⠉⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣷⡄⠀⠀⠠⣍⡛⠶⣤⣄⡀⠀⠀⡾⠁⠀⠀⠀⠀⢠⡟⠀⠀⠀⣀⣴⡿⠛⠁⠀⠀⠀⢀⣴⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠄⠒⠉⠁
⠱⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣦⣀⠀⠀⠉⠒⠤⢍⣛⠳⠾⠷⢤⣤⣤⣤⣤⣾⣤⡴⠶⠟⠋⠁⠀⠀⠀⠀⢀⣴⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀
⠀⢣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣷⣶⣤⣤⣀⣤⣄⣀⠀⠐⠒⠒⠂⠤⠤⠤⠄⠐⠀⠀⠀⢀⣀⣠⣴⣾⡿⢋⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠐⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣯⠉⠛⠿⣿⣷⣍⠙⠻⣿⠿⠿⢿⣿⣷⣶⣿⣷⣶⣶⣶⣶⡶⣾⣿⣿⡿⢿⣿⣿⣶⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣷⠀⠀⠈⠉⠛⠿⣦⣅⠀⠀⠀⠈⠉⠉⠉⠉⣿⣿⣿⣿⡷⠿⠋⠁⢀⣾⣿⡟⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⡆⠀⠀⠀⠀⠀⠈⠙⢿⣦⡀⠀⠀⣀⣀⣤⣾⠿⠛⠁⠀⠀⠀⢠⣾⣷⠏⢸⣿⠃⠀⠀⠀⠀⠀⠀⠀⢰⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡇⠠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣯⢿⣄⠀⠀⠀⠀⠀⠀⠀⠉⠻⣦⣀⣉⣽⠟⠁⠀⠀⠀⠀⠀⢠⣿⣿⠏⠀⣾⣿⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣦⡙⢿⣶⣤⡄⠀⠀⠀⠀⠀⣀⡙⣓⡀⠀⠀⠀⠀⢀⣴⣴⣿⣿⠋⠀⠀⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
 */
#define yon(x) cout<<((x)?"YES\n":"NO\n"); 
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend() 
#define ff first 
#define ss second 
#define em emplace 
#define emp emplace_back 
#define pb push_back
#define rep(i,j,k) for(int i=j;i<=k;i++) 
#define per(i,j,k) for(int i=k;i>=j;i--) 
#define forp(x,y,a) for(auto &[x,y]:(a)) 
#define mkp make_pair
typedef long long  ll; 
typedef pair<ll,ll> pll; 
typedef vector<ll> vl; 
typedef vector<pll> vpl; 
typedef vector<vl> vvl; 
typedef vector<vpl> vvpl; 
typedef vector<string> vs; 
typedef vector<set<ll> >vst;
typedef deque<ll> dl; 

const ll inf =1e18+1; 
const int N=1e6+1; 
const ll dx[]={1,0,-1,0};
const ll dy[]={0,1,0,-1,0}; 
const ll mod=1e9+7;
char dir[]={'D','R','U','L'};
   
void solve(){
  ll n;
  cin>>n;
  vector<array<double,3> >a(n);
  rep(i,0,n-1){
    cin>>a[i][0]>>a[i][1];
    a[i][2]=i;
  }
  vector<double> ans(n);
  stack<pair<double,double>>st;
  rep(i,0,n-1){
 double mx=a[i][1];
 while(!st.empty()){
pair<double,double>c=st.top();
double cr=pow(c.ff-a[i][0],2)/(4*c.ss);
mx=min(mx,cr);
 
  if(mx>=c.ss){
    st.pop();
  }else{
break;
  }
  }
  ans[i]=mx;
  st.em(a[i][0],mx);
  }
for(auto &it:ans){
  cout<<fixed<<setprecision(3)<<it<<"\n";
}
}
signed main(){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
  
    #ifdef Usaco 
    string f="fencedin"; 
    freopen((f+".in").c_str(),"r",stdin); 
    freopen((f+".out").c_str(),"w",stdout); 
    #endif 
    int t = 1; 
   //cin >> t; 
   
    while (t--) { 
        solve(); 
        
           
        
    } 
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⣿⣿⠀⠀⠀⢠⣾⣧⣤⡖⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⠋⠀⠉⠀⢄⣸⣿⣿⣿⣿⣿⣥⡤⢶⣿⣦⣀⡀
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⡆⠀⠀⠀⣙⣛⣿⣿⣿⣿⡏⠀⠀⣀⣿⣿⣿⡟
⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⠷⣦⣤⣤⣬⣽⣿⣿⣿⣿⣿⣿⣿⣟⠛⠿⠋⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⠋⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⡆⠀⠀
⠀⠀⠀⠀⣠⣶⣶⣶⣿⣦⡀⠘⣿⣿⣿⣿⣿⣿⣿⣿⠿⠋⠈⢹⡏⠁⠀⠀
⠀⠀⠀⢀⣿⡏⠉⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡆⠀⢀⣿⡇⠀⠀⠀
⠀⠀⠀⢸⣿⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣟⡘⣿⣿⣃⠀⠀⠀
⣴⣷⣀⣸⣿⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⠹⣿⣯⣤⣾⠏⠉⠉⠉⠙⠢⠀
⠈⠙⢿⣿⡟⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣄⠛⠉⢩⣷⣴⡆⠀⠀⠀⠀⠀
⠀⠀⠀⠋⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⣿⣀⡠⠋⠈⢿⣇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10