Submission #1338494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338494		xnoel	Mobile (BOI12_mobile)	C++20	0 / 100	766 ms	33028 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

double findx(double x1, double y1, double x2, double y2){
    double xm = (x1+x2)/2, ym = (y1+y2)/2;
    double k=(y2-y1)/(x2-x1);
    return xm+ym*k;
}

int main(){
    //freopen("1.in","r",stdin);
    int n;
    cin>>n;
    double len;
    cin>>len;
    stack<pair<double,double>> xpoints;
    stack<pair<double,double>> mobiles;
    double last_x,last_y; 
    cin>>last_x>>last_y;
    xpoints.push({0,sqrt(last_x*last_x+last_y*last_y)});
    mobiles.push({last_x,last_y});
    for (int i=1;i<n;i++) {
        double next_x,next_y;
        cin>>next_x>>next_y;
        if (next_x==last_x) continue;
        while (!xpoints.empty()){
            double new_dist = sqrt((next_x-xpoints.top().first)*(next_x-xpoints.top().first)+next_y*next_y);
            //cout<<"new_dist: "<<new_dist<<"  xpoints.top().first: "<<xpoints.top().first<<" xpoints.top().second: "<<xpoints.top().second<<"\n";
            if (new_dist<xpoints.top().second) {
                xpoints.pop();
                mobiles.pop();
            }
            else break;
        }
        if (xpoints.empty()) {
            xpoints.push({0,sqrt(next_x*next_x+next_y*next_y)});
            mobiles.push({next_x,next_y});
        }
        else {
            double stack_x = mobiles.top().first;
            double stack_y = mobiles.top().second;
            double new_x = findx(stack_x,stack_y,next_x,next_y);
            double new_dist = sqrt((new_x-next_x)*(new_x-next_x)+(next_y*next_y));
            xpoints.push({new_x,new_dist});
            mobiles.push({next_x,next_y});
            //cout<<"new_x: "<<new_x<<" new_dist: "<<new_dist<<"\n";
        }
        last_x=next_x;
        last_y=next_y;
    }

    double ans=0;
    while (!xpoints.empty()){
        //cout<<xpoints.top().first<<" "<<xpoints.top().second<<"\n";
        ans=max(ans,xpoints.top().second);
        xpoints.pop();
    }
    //cout<<"\n";
    
    double dist_to_last=1e9;
    while (!mobiles.empty()){
        //cout<<mobiles.top().first<<" "<<mobiles.top().second<<"\n";
        double curr_x = mobiles.top().first;
        double curr_y = mobiles.top().second;
        double curr_dis = sqrt((len-curr_x)*(len-curr_x) + curr_y*curr_y);
        dist_to_last = min(dist_to_last, curr_dis);        
        mobiles.pop();
    }
    ans=max(ans,dist_to_last);
    cout<<fixed<<setprecision(10)<<ans<<"\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5