Submission #962513

#	Time	Username	Problem	Language	Result	Execution time	Memory
962513		VKnight	Balloons (CEOI11_bal)	C++17	0 / 100	132 ms	7220 KiB

bal

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define gett(tup,ind) get<ind>(tup)
#define print(x) for (auto i:x){cout<<i<<endl;};

using namespace std;

bool check(int x1,double r1,int x2,double r2){
    double dis=(x1-x2)*(x1-x2)+(r1-r2)*(r1-r2);
    return (r1+r2)*(r1+r2)<=dis;
}

double rad(int x1,double r1,int x2,double r2){

    if (check(x1,r1,x2,r2))return r2;

    double strt=0,ans=0;
    while (strt+0.0001<=r2){
        double mid=strt+(r2-strt)/2;
        if (check(x1,r1,x2,mid)){ans=mid;strt=mid;}
        else{r2=mid;}
    }

    return ans;
}

void solve(){
    int n;cin>>n;

    vector <int> pos(n),lim(n);
    for (int i=0;i<n;i++)cin>>pos[i]>>lim[i];

    vector <double> ans(n);
    stack <int> stk;

    for (int i=0;i<n;i++){
        double r=lim[i];
        while (stk.size() && !check(pos[stk.top()],ans[stk.top()],pos[i],r)){r=rad(pos[stk.top()],ans[stk.top()],pos[i],r);stk.pop();}
        ans[i]=r;
        stk.emplace(i);
    }

    cout<<setprecision(4);

    print(ans);

    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    int no_test=1;
    //cin>>no_test;
    while (no_test--){solve();}
    return 0;
}

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