Submission #1225504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225504		AlgorithmWarrior	Mobile (BOI12_mobile)	C++20	0 / 100	521 ms	73828 KiB

mobile

#include <bits/stdc++.h>
#define ld long double

using namespace std;

struct range{
    ld x,y,l,r;
};

ld special_inters(ld x1,ld y1,ld x2,ld y2){
    return (x1*x1-x2*x2+y1*y1-y2*y2)/(2*(x1-x2));
}

vector<range>range;
int n,len;
int const NMAX=1000005;
struct point{
    int x,y;
}points[NMAX];

void read(){
    cin>>n>>len;
    int i;
    for(i=1;i<=n;++i)
        cin>>points[i].x>>points[i].y;
}

void get_range(){
    int i;
    for(i=1;i<=n;++i){
        int x=points[i].x,y=abs(points[i].y);
        while(i<n && x==points[i+1].x){
            ++i;
            if(y>abs(points[i].y))
                y=abs(points[i].y);
        }
        while(!range.empty()){
            auto [px,py,l,r]=range.back();
            ld inters=special_inters(x,y,px,py);
            if(r<=inters)
                break;
            if(inters<=l)
                range.pop_back();
            else{
                range.back().r=inters;
                break;
            }
        }
        if(range.empty())
            range.push_back({(ld)x,(ld)y,0,(ld)len});
        else
            range.push_back({(ld)x,(ld)y,range.back().r,(ld)len});
    }
}

ld dist(ld x1,ld y1,ld x2,ld y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

ld solve(){
    ld mxm=0;
    for(auto [x,y,l,r] : range){
        ld dst=dist(x,y,l,0);
        if(mxm<dst)
            mxm=dst;
        dst=dist(x,y,r,0);
        if(mxm<dst)
            mxm=dst;
    }
    return mxm;
}

int main()
{
    read();
    get_range();
    cout<<fixed<<setprecision(6)<<solve();
    return 0;
}

• 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