oj.uz

답안 #1045642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045642 2024-08-06T06:41:10 Z VectorLi Mobile (BOI12_mobile) C++17
0 / 100
 449 ms 8268 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = (int) 1E6;

int n, k;
int x[N], y[N];

/*
为什么这么做的对的，考虑排序线段。
我们排序线段的目的就是为了 连的上！
所以如果线段 i 在 j 之后出现
且 l(i) < l(j)
一定有 r(i) > r(j)，这就保证了我们不需要使用排序 
*/

bool valid(double a) {
	double t = 0;
	// t 表示已经可以覆盖 [0, t] 了，初始为空区间 
	// 因为输入的点的坐标是有序的，所以如果当前的 r 只能覆盖线段
	// 的中段的话，t 还会保持是 0 
	for (int i = 0; i < n; i++) {
		double l = x[i] - sqrt(1.0 * a * a - 1.0 * y[i] * y[i]);
		// 直接 y[i] * y[i] 可能会爆
		// 同时，由于 r 大于最大的 abs(y[i])，所以不会出现 sqrt 负数的情况 
		double r = x[i] + sqrt(1.0 * a * a - 1.0 * y[i] * y[i]);
		if (l <= t && r >= t) {
			t = r;
		}
	}
	return t >= k;
}

void solve() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	
	double l = 0, r = 2E9;
	for (int i = 0; i < n; i++) {
		l = max(l, 1.0 * abs(y[i]));
	}
	for (int i = 0; i < 100; i++) {
		double m = (l + r) / 2;
		if (valid(m)) {
			r = m;
		} else {
			l = m;
		}
	}
	cout << fixed << setprecision(6);
	cout << r << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2520 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 2 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 4748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 4720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 4700 KB Output is correct
2 Correct 39 ms 4700 KB Output is correct
3 Incorrect 29 ms 4696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 6748 KB Output is correct
2 Correct 46 ms 6744 KB Output is correct
3 Incorrect 37 ms 6744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 6748 KB Output is correct
2 Correct 46 ms 6748 KB Output is correct
3 Incorrect 33 ms 6744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 6992 KB Output is correct
2 Correct 178 ms 6748 KB Output is correct
3 Correct 173 ms 6748 KB Output is correct
4 Incorrect 185 ms 6780 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 6748 KB Output is correct
2 Incorrect 170 ms 6744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 7000 KB Output is correct
2 Correct 220 ms 6748 KB Output is correct
3 Correct 214 ms 6744 KB Output is correct
4 Incorrect 225 ms 7000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 6744 KB Output is correct
2 Incorrect 249 ms 6800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 6992 KB Output is correct
2 Correct 243 ms 7056 KB Output is correct
3 Correct 240 ms 6992 KB Output is correct
4 Incorrect 287 ms 7032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 6992 KB Output is correct
2 Incorrect 245 ms 6864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 314 ms 7300 KB Output is correct
2 Correct 280 ms 7288 KB Output is correct
3 Correct 293 ms 7340 KB Output is correct
4 Incorrect 301 ms 7248 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 7484 KB Output is correct
2 Incorrect 275 ms 7252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 8072 KB Output is correct
2 Correct 362 ms 8056 KB Output is correct
3 Correct 353 ms 8068 KB Output is correct
4 Incorrect 449 ms 8268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 8056 KB Output is correct
2 Incorrect 371 ms 8260 KB Output isn't correct
3 Halted 0 ms 0 KB -