제출 #1338613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338613		xnoel	Mobile (BOI12_mobile)	C++20	0 / 100	1097 ms	32552 KiB

mobile

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

int n;
double len;
vector<pair<int, int>> points;
vector<pair<double,double>> compressed_points;


pair<double,double> findx(int x, int y, double dist){
    double newx=double(x);
    double newy=double(y);
    if (dist<abs(newy)) return {-1,-1};
    double diff=sqrt(dist*dist-newy*newy);
    return {newx-diff,newx+diff};
}

bool alg(double dist){
    stack<pair<double,double>> st;
    for (auto [x,y]:compressed_points) {
        auto [x1,x2]=findx(x,y,dist);
        if (x1==-1) continue;
        if (x2<0 || x1>len) continue;
        while (!st.empty() && st.top().second>x1) {
            st.pop();
        }
        if (st.empty()) st.push({x1,x2});
        else if (st.top().second>=x1) st.push({x1,x2});
    }
    if (st.empty()) return false;
    return st.top().second>=len;
}


signed main(){
    //freopen("1.in","r",stdin);
    cin>>n>>len;
    points.resize(n);
    for (int i=0;i<n;i++) cin>>points[i].first>>points[i].second;
    sort(points.begin(),points.end(),[](const pair<double,double>& a, const pair<double,double>& b) {
        if (a.first==b.first) return (a.second)*(a.second)<(b.second)*(b.second);
        return a.first<b.first;
    });
    int prev_x=-1e9-10;
    for (auto [x,y]:points) {
        if (x==prev_x) continue;
        prev_x=x;
        compressed_points.push_back({double(x),double(y)});
    }

    // for (auto [x,y]:compressed_points) {
    //     cout<<x<<" "<<y<<endl;
    // }
    // cout<<"\n";

    double left=0,right=len;
    while (right-left>1e-6){
        double mid=left+(right-left)/2;
        if (alg(mid)) right=mid;
        else left=mid;
    }
    cout<<left<<"\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