Submission #1083689

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1083689	2024-09-03T20:28:10 Z	vjudge1	Mobile (BOI12_mobile)	C++17	90 / 100	1000 ms	30920 KB

mobile

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

// Function to check if all points on the highway [0, L] can be covered with distance R
bool canCoverAllPoints(const vector<pair<double, double>>& stations, double R, double L) {
    double coverageEnd = 0.0;
    
    for (const auto& station : stations) {
        double xi = station.first;
        double yi = station.second;
        
        if (yi > R) continue; // This base station cannot cover the highway at distance R
        
        double reach = sqrt(R * R - yi * yi);
        double startCoverage = xi - reach;
        double endCoverage = xi + reach;
        
        // Extend the current coverage
        if (startCoverage <= coverageEnd) {
            coverageEnd = max(coverageEnd, endCoverage);
        }
        
        if (coverageEnd >= L) return true;
    }
    
    return coverageEnd >= L;
}

int main() {
    int N;
    double L;
    cin >> N >> L;

    vector<pair<double, double>> stations(N);
    for (int i = 0; i < N; ++i) {
        double xi, yi;
        cin >> xi >> yi;
        stations[i] = {xi, yi};
    }

    // Binary search for the smallest possible R
    double low = 0.0;
    double high = 1e9;
    double epsilon = 1e-6; // Precision for the binary search

    while (high - low > epsilon) {
        double mid = (low + high) / 2.0;
        if (canCoverAllPoints(stations, mid, L)) {
            high = mid; // Try smaller radius
        } else {
            low = mid; // Increase radius
        }
    }

    cout << fixed << setprecision(6) << high << endl;
    return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 ms	348 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	348 KB	Output is correct
2	Correct	3 ms	348 KB	Output is correct
3	Correct	4 ms	860 KB	Output is correct
4	Correct	4 ms	348 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	348 KB	Output is correct
2	Correct	3 ms	448 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	4 ms	348 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	348 KB	Output is correct
2	Correct	4 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	5 ms	448 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	2388 KB	Output is correct
2	Correct	47 ms	2640 KB	Output is correct
3	Correct	28 ms	1884 KB	Output is correct
4	Correct	66 ms	2756 KB	Output is correct
5	Correct	24 ms	1368 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	2296 KB	Output is correct
2	Correct	52 ms	2140 KB	Output is correct
3	Correct	80 ms	2640 KB	Output is correct
4	Correct	67 ms	2644 KB	Output is correct
5	Correct	78 ms	3180 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	2384 KB	Output is correct
2	Correct	50 ms	2860 KB	Output is correct
3	Correct	46 ms	2896 KB	Output is correct
4	Correct	97 ms	3924 KB	Output is correct
5	Correct	56 ms	2740 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	3408 KB	Output is correct
2	Correct	64 ms	3396 KB	Output is correct
3	Correct	51 ms	2900 KB	Output is correct
4	Correct	103 ms	3780 KB	Output is correct
5	Correct	80 ms	3012 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	3408 KB	Output is correct
2	Correct	61 ms	3392 KB	Output is correct
3	Correct	57 ms	3016 KB	Output is correct
4	Correct	106 ms	3928 KB	Output is correct
5	Correct	75 ms	3156 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	282 ms	12116 KB	Output is correct
2	Correct	349 ms	15196 KB	Output is correct
3	Correct	305 ms	15000 KB	Output is correct
4	Correct	506 ms	15724 KB	Output is correct
5	Correct	402 ms	13392 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	413 ms	14672 KB	Output is correct
2	Correct	367 ms	13648 KB	Output is correct
3	Correct	316 ms	12768 KB	Output is correct
4	Correct	513 ms	15668 KB	Output is correct
5	Correct	432 ms	14136 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	344 ms	14160 KB	Output is correct
2	Correct	396 ms	17236 KB	Output is correct
3	Correct	370 ms	16684 KB	Output is correct
4	Correct	612 ms	19260 KB	Output is correct
5	Correct	476 ms	16064 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	430 ms	17416 KB	Output is correct
2	Correct	465 ms	15952 KB	Output is correct
3	Correct	365 ms	15092 KB	Output is correct
4	Correct	668 ms	19020 KB	Output is correct
5	Correct	504 ms	16516 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	16116 KB	Output is correct
2	Correct	479 ms	19632 KB	Output is correct
3	Correct	484 ms	19288 KB	Output is correct
4	Correct	728 ms	21752 KB	Output is correct
5	Correct	562 ms	18460 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	506 ms	20308 KB	Output is correct
2	Correct	492 ms	18808 KB	Output is correct
3	Correct	400 ms	18012 KB	Output is correct
4	Correct	698 ms	21716 KB	Output is correct
5	Correct	596 ms	19208 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	18576 KB	Output is correct
2	Correct	567 ms	22612 KB	Output is correct
3	Correct	508 ms	22160 KB	Output is correct
4	Correct	848 ms	25176 KB	Output is correct
5	Correct	666 ms	21656 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	593 ms	22956 KB	Output is correct
2	Correct	565 ms	21376 KB	Output is correct
3	Correct	445 ms	20480 KB	Output is correct
4	Correct	884 ms	24916 KB	Output is correct
5	Correct	691 ms	22160 KB	Output is correct

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	613 ms	22868 KB	Output is correct
2	Correct	676 ms	27988 KB	Output is correct
3	Correct	672 ms	27348 KB	Output is correct
4	Execution timed out	1090 ms	30544 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	733 ms	28692 KB	Output is correct
2	Correct	752 ms	26192 KB	Output is correct
3	Correct	584 ms	25424 KB	Output is correct
4	Execution timed out	1004 ms	30920 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Submission #1083689

Compilation message