제출 #1338619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338619		xnoel	Mobile (BOI12_mobile)	C++20	90 / 100	1096 ms	47432 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){
    vector<pair<double,double>> vp;
    vp.reserve(compressed_points.size());
    for (auto [x,y]:compressed_points) {
        auto [x1,x2]=findx(x,y,dist);
        if (x1==-1) continue;
        if (x2<0 || x1>len) continue;
        vp.push_back({x1,x2});       
    }
    if (vp.empty()) return false;
    sort(vp.begin(),vp.end());
    if (vp[0].first>0) return false;
    double max_reached=vp[0].second;
    for (int i=1;i<vp.size();i++) {
        if (vp[i].first<=max_reached) max_reached=max(max_reached,vp[i].second);
        if (max_reached>=len) return true;
    }
    return false;    
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
     //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=1e9;
    while (right-left>1e-3){
        double mid=left+(right-left)/2;
        if (alg(mid)) right=mid;
        else left=mid;
    }
    cout<<fixed<<setprecision(4)<<right<<"\n";
    
}

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