답안 #445978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445978	2021-07-20T10:20:47 Z	Qw3rTy	Mobile (BOI12_mobile)	C++11	100 / 100	833 ms	34736 KB

mobile

#include <bits/stdc++.h>
#define int long long
#define db double
#define delta 1e-6
#define pi pair<int,int>
#define pb pair<db,db>
#define fi first
#define se second
using namespace std;

const int maxN = 1e6+5;

int N,L;
pi tower[maxN];
pb inter[maxN]; //intersections

bool works(db r){
	for(int i = 1; i <= N; ++i) {
		inter[i].fi = tower[i].fi - sqrt(r*r - tower[i].se*tower[i].se);
		inter[i].se = tower[i].fi + sqrt(r*r - tower[i].se*tower[i].se);
	}
	db curr = 0;
	for(int i = 1; i <= N; ++i){
		if(inter[i].fi > inter[i].se)continue;
		if(inter[i].fi <= curr)curr = max(curr,inter[i].se);
	}
	if(curr >= L)return true;
	return false;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("../test.in","r",stdin);
	cin >> N >> L;
	for(int i = 1; i <= N; ++i)cin >> tower[i].fi >> tower[i].se;
	db low = 1; db high = L;
	while(abs(high-low) > delta){
		db mid = (low+high)/2;
		if(works(mid))high = mid;
		else low = mid + delta;
	}
	cout << setprecision(12) << low  << '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	320 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	460 KB	Output is correct
2	Correct	3 ms	452 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	4 ms	460 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	460 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	3 ms	412 KB	Output is correct
4	Correct	5 ms	460 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	460 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	4 ms	460 KB	Output is correct
5	Correct	3 ms	460 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	2816 KB	Output is correct
2	Correct	38 ms	2908 KB	Output is correct
3	Correct	25 ms	2188 KB	Output is correct
4	Correct	54 ms	2764 KB	Output is correct
5	Correct	24 ms	2036 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	2888 KB	Output is correct
2	Correct	43 ms	2608 KB	Output is correct
3	Correct	53 ms	2964 KB	Output is correct
4	Correct	60 ms	2884 KB	Output is correct
5	Correct	63 ms	3168 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	3248 KB	Output is correct
2	Correct	40 ms	3152 KB	Output is correct
3	Correct	40 ms	3228 KB	Output is correct
4	Correct	81 ms	3504 KB	Output is correct
5	Correct	55 ms	3300 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	3604 KB	Output is correct
2	Correct	49 ms	3648 KB	Output is correct
3	Correct	43 ms	3600 KB	Output is correct
4	Correct	81 ms	3644 KB	Output is correct
5	Correct	63 ms	3564 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	3584 KB	Output is correct
2	Correct	48 ms	3560 KB	Output is correct
3	Correct	43 ms	3524 KB	Output is correct
4	Correct	82 ms	3580 KB	Output is correct
5	Correct	63 ms	3404 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	15932 KB	Output is correct
2	Correct	244 ms	15940 KB	Output is correct
3	Correct	228 ms	15940 KB	Output is correct
4	Correct	430 ms	15968 KB	Output is correct
5	Correct	386 ms	15944 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	270 ms	15940 KB	Output is correct
2	Correct	444 ms	15968 KB	Output is correct
3	Correct	255 ms	16036 KB	Output is correct
4	Correct	418 ms	15972 KB	Output is correct
5	Correct	390 ms	16032 KB	Output is correct

Subtask #14
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	19016 KB	Output is correct
2	Correct	316 ms	19164 KB	Output is correct
3	Correct	286 ms	22364 KB	Output is correct
4	Correct	511 ms	22220 KB	Output is correct
5	Correct	404 ms	22432 KB	Output is correct

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	325 ms	19192 KB	Output is correct
2	Correct	527 ms	19220 KB	Output is correct
3	Correct	287 ms	19076 KB	Output is correct
4	Correct	486 ms	19168 KB	Output is correct
5	Correct	415 ms	19124 KB	Output is correct

Subtask #16
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	22228 KB	Output is correct
2	Correct	360 ms	22296 KB	Output is correct
3	Correct	331 ms	25356 KB	Output is correct
4	Correct	585 ms	25364 KB	Output is correct
5	Correct	457 ms	25496 KB	Output is correct

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	386 ms	22232 KB	Output is correct
2	Correct	596 ms	22340 KB	Output is correct
3	Correct	336 ms	22232 KB	Output is correct
4	Correct	556 ms	22152 KB	Output is correct
5	Correct	492 ms	22212 KB	Output is correct

Subtask #18
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	372 ms	25412 KB	Output is correct
2	Correct	412 ms	25488 KB	Output is correct
3	Correct	378 ms	28584 KB	Output is correct
4	Correct	669 ms	28448 KB	Output is correct
5	Correct	542 ms	28612 KB	Output is correct

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	433 ms	25440 KB	Output is correct
2	Correct	663 ms	25280 KB	Output is correct
3	Correct	421 ms	25372 KB	Output is correct
4	Correct	659 ms	25440 KB	Output is correct
5	Correct	543 ms	25288 KB	Output is correct

Subtask #20
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	494 ms	31608 KB	Output is correct
2	Correct	537 ms	31676 KB	Output is correct
3	Correct	476 ms	34704 KB	Output is correct
4	Correct	833 ms	31704 KB	Output is correct
5	Correct	698 ms	34736 KB	Output is correct

Subtask #21
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	567 ms	31604 KB	Output is correct
2	Correct	812 ms	31664 KB	Output is correct
3	Correct	491 ms	31556 KB	Output is correct
4	Correct	832 ms	31640 KB	Output is correct
5	Correct	720 ms	31608 KB	Output is correct

답안 #445978

Compilation message