Submission #1352874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352874		vahagng	Mobile (BOI12_mobile)	C++20	0 / 100	1097 ms	80968 KiB

mobile

#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;

Point a[N];

bool check(ld m){
    vector<pair<ld, ld>>A;
    for(int i = 1; i <= n; i++){
        ld d = sqrt(m * m - a[i].y * a[i].y);
        A.push_back({a[i].x - d, a[i].x + d});
    }
    if(A[0].first > 0){
        return 0;
    }
    if(A[n - 1].second < l){
        return 0;
    }
    for(int i = 1; i < n; i++){
        if(!(A[i - 1].second >= A[i].first)){
            return 0;
        }
    }
    return 1;
}

int main(){
    cin >> n >> l;
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y;
    }
    ld l = 0.0, r = 1e10, ans = -1;
    for(int it = 0; it < 100; it++){
        ld m = (l + r) / 2.0;
        if(check(m)){
            r = m - 1;
            ans = m;
        }else{
            l = m + 1;
        }
    }
    precision(20);
    cout << ans << endl;
}

• 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