oj.uz

Submission #684604

# Submission time Handle Problem Language Result Execution time Memory
684604 2023-01-22T00:55:01 Z aaggupta07 Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 15956 KB 
// Source: https://usaco.guide/general/io

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

#define int long long
#define double long double
#define f first
#define s second
#define mp make_pair

constexpr int MAX_C = 1.5e9;
constexpr int MAX_N = 1e6;
constexpr double tol = 0.00000001L;

using pi = pair<int, int>;
using pd = pair<double, double>;

int n, l;
pi towers[MAX_N];

bool doubleEq(double a, double b) {
	return abs(a - b) <= tol;
}

double calcDist(int i, double d) {
	return sqrt((d * d) - (towers[i].s * towers[i].s));
}

bool check(double p) {
	// cout << "Called: " << p << endl;

	double best = 0;
	for(int i = 0; i < n; ++i) {
		if(abs(towers[i].s) >= p || doubleEq(abs(towers[i].s), p)) continue;

		double dist = calcDist(towers[i].s, p), d1 = towers[i].f - dist, d2 = towers[i].f + dist;
		// if(p - 6.98 <= 0.1) cout << d1 << ' ' << d2 << endl;

		if(d1 < best || doubleEq(d1, best)) best = max(best, d2);
	}

	// if(p - 6.98 <= 0.1) {
	// 	cout << "------------------" << endl;
	// 	cout << start << ' ' << curEnd << '\n';
	// 	// for(int i = 0; i < n; ++i) cout << intervals[i].f << ' ' << intervals[i].s << endl;
	// 	cout << "------------------" << endl;
	// }

	if(best > l || doubleEq(best, l)) return true;
	return false;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> l;
	for(int i = 0; i < n; ++i) cin >> towers[i].f >> towers[i].s;
	
	double le = 0, r = MAX_C;
	while(r - le >= 1e-3) {
		double mid = (le + r) / 2;
		if(check(mid)) r = mid;
		else le = mid;
	}
	
	cout.precision(4);
	cout << fixed << le << '\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 1404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1684 KB Output is correct
2 Incorrect 42 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 1892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 8132 KB Output is correct
2 Incorrect 444 ms 8132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 8136 KB Output is correct
2 Incorrect 355 ms 8312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 9664 KB Output is correct
2 Incorrect 666 ms 9704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 927 ms 9704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 11200 KB Output is correct
2 Incorrect 840 ms 11264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 11264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 12836 KB Output is correct
2 Execution timed out 1030 ms 12836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 12724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 15956 KB Output is correct
2 Execution timed out 1085 ms 15948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 15892 KB Time limit exceeded
2 Halted 0 ms 0 KB -