Submission #1352871

#TimeUsernameProblemLanguageResultExecution timeMemory
1352871vahagngMobile (BOI12_mobile)C++20
0 / 100
1099 ms159260 KiB
#include <bits/stdc++.h>
using namespace std;

#define ld long double

struct Point{
    ld x, y;

};

ld dist(Point A, Point B){
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

struct Line{
    ld k, b;

    Point X_intersect(){
        return Point{-b / k * 1.0, 0.0};
    }
};

Line ln(Point A, Point B){
    // y1 = k*x1 + b
    // y2 = k*x2 + b
    // y1 - y2 = k(x1 - x2)
    // k = (y1 - y2) / (x1 - x2)
    ld K = (A.y - B.y) / (A.x - B.x);
    ld BB = A.y - K*A.x;
    return Line{K, BB};
}

Line mijnuxahayac(Point A, Point B){
    auto [K, BB] = ln(A, B);
    Point M = {(A.x + B.x) / 2.0, (A.y + B.y) / 2.0};
    ld K1 = -1.0 / K;
    ld BB1 = M.y - K1*M.x;
    return Line{K1, BB1};        
}

void precision(int x){
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(x);
	return;
}

const int N = 1e6 + 10;

int n, l;

int main(){
    cin >> n >> l;
    map<ld,ld> mp;
    precision(20);
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        if(mp.find(x) != mp.end()){
            if(abs(mp[x]) > abs(y)){
                mp[x] = y;
            }
        }else{
            mp[x] = y;
        }
    }
    vector<Point> A;
    for(auto i : mp){
        // cerr << i.first << ' ' << i.second << endl;
        A.push_back(Point{i.first, i.second});
    }
    if(A.size() == 1){
        cout << max(dist(Point{0, 0}, A[0]), dist(Point{(ld)l, 0}, A[0])) << endl;
        return 0;
    }
    vector<Point> pts;
    int id = -1;
    for(int i = 1; i < A.size(); i++){
        Line L = mijnuxahayac(A[i - 1], A[i]);
        Point X = L.X_intersect();
        if(X.x < 0) continue;
        if(id == -1){
            id = i - 1;
        }
        pts.push_back(X);
    }
    // for(auto i : pts){
    //     cerr << i.x << ' ' << i.y << endl;
    // }
    if(id == -1){
        cout << max(dist(Point{0, 0}, A.back()), dist(Point{(ld)l, 0}, A.back())) << endl;
        return 0;
    }
    ld ans = 0;
    for(int i = 0; i < pts.size(); i++){
        if(i == 0){
            // cerr << dist({0, 0}, A[id]) << endl;
            // cerr << dist(pts[i], A[id]) << endl;
            ans = max({ans, dist({0, 0}, A[id]), dist(pts[i], A[id])});
        }else{
            ans = max({ans, dist(pts[i - 1], A[id]), dist(pts[i], A[id])});
        }
        id++;
    }
    // cerr << dist(pts[pts.size() - 1], A[id]) << endl;
    // cerr << dist({(ld)l, 0}, A[id]) << endl;
    ans = max({ans, dist(pts[pts.size() - 1], A[id]), dist({(ld)l, 0}, A[id])});
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...