Submission #1252094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252094		abc	Balloons (CEOI11_bal)	C++20	0 / 100	284 ms	6500 KiB

bal

#include <bits/stdc++.h>
using namespace std;
int MOD = 1e9+7;
double MUL = 1e-3;
bool check(double r1, double r2 , double x1 , double x2)
{
    double y =  (r1-r2);
    double x = (x1-x2);
    double r  = (r1+r2);
    
    return 1ll*r*r < (1ll*x*x + 1ll*y*y);
}

double get_ht(double x1,double x2 , double r1 )
{
    return float(((x1-x2)*(x1-x2))/(4*r1));
}

int main() {
	// your code goes here
    int n;
    
    cin>>n;
    
    vector<pair<double,double>>arr(n);
    for(int i=0;i<n;i++)
    {
        cin>>arr[i].first>>arr[i].second;
    }
    
    vector<pair<double,double>>stk;
    
    vector<double>res(n,0);
    res[0] = arr[0].second;
    
    stk.push_back({arr[0].first,arr[0].second});
    
    for(int i=1;i<n;i++)
    {
        
        double mnx=arr[i].second;
        while(!stk.empty() && !check(stk.back().second,arr[i].second,stk.back().first,arr[i].first))
        {
            double ht = get_ht(stk.back().first,arr[i].first,stk.back().second);
            if(mnx>ht)
            {
                mnx = ht;
            }
            stk.pop_back();
        }
        res[i]=mnx;
        stk.push_back({arr[i].first,mnx});
    }
    
    for(int i=0;i<n;i++)
    {
        cout<<setprecision(4)<<res[i]<<endl;
    }
    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