Submission #00363

ソースコード

#include <bits/stdc++.h>
  
using namespace std;
  
int N;
long long X[100000], R[100000];
  
bool check(double mid)
{
  double l = -1e18, r = 1e18;
  for(int i = 0; i < N; i++) {
    if(R[i] - mid < 0) return(false);
    double width = sqrt(R[i] - mid);
    l = max(l, X[i] - width);
    r = min(r, X[i] + width);
  }
  return(l < r);
}
int main()
{
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%lld %lld", &X[i], &R[i]);
    R[i] *= R[i];
  }
  double low = 0, high = *min_element(R, R + N);
  for(int i = 0; i < 50; i++) {
    double mid = (low + high) / 2;
    if(check(mid)) low = mid;
    else high = mid;
  }
  printf("%.8lf", sqrt(low));
}

ステータス

項目	データ
問題	0009 - ヒバラ海に沈む遺跡
ユーザー名	ei1333
投稿日時	2016-08-29 11:49:48
言語	C++11
状態	Accepted
得点	16
ソースコード長	692 Byte
最大実行時間	63 ms
最大メモリ使用量	2308 KB

セット

	セット	得点	Cases
1	ALL	16 / 16	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
00-sample1.in	AC	23 ms	476 KB	1
00-sample2.in	AC	22 ms	700 KB	1
00-sample3.in	AC	23 ms	544 KB	1
01_shift1.in	AC	63 ms	2180 KB	1
01_shift10.in	AC	59 ms	2136 KB	1
01_small_00.in	AC	22 ms	556 KB	1
01_small_01.in	AC	13 ms	528 KB	1
02_single1.in	AC	19 ms	368 KB	1
02_single2.in	AC	23 ms	468 KB	1
02_single3.in	AC	16 ms	568 KB	1
10_common1.in	AC	56 ms	2148 KB	1
10_common2.in	AC	51 ms	2236 KB	1
20_small_area1.in	AC	59 ms	2192 KB	1
20_small_area2.in	AC	56 ms	2272 KB	1
30_nest_center.in	AC	59 ms	2228 KB	1
30_nest_left.in	AC	58 ms	2308 KB	1
30_nest_right.in	AC	61 ms	2264 KB	1
100_rand_00.in	AC	21 ms	668 KB	1
100_rand_01.in	AC	22 ms	640 KB	1
100_rand_02.in	AC	23 ms	484 KB	1
100_rand_03.in	AC	18 ms	580 KB	1
100_rand_04.in	AC	21 ms	552 KB	1
100_rand_05.in	AC	14 ms	520 KB	1
100_rand_06.in	AC	16 ms	620 KB	1
100_rand_07.in	AC	19 ms	592 KB	1
100_rand_08.in	AC	19 ms	564 KB	1
100_rand_09.in	AC	22 ms	540 KB	1
100_rand_10.in	AC	17 ms	512 KB	1
101_largerand_00.in	AC	20 ms	616 KB	1
101_largerand_01.in	AC	18 ms	576 KB	1
101_largerand_02.in	AC	23 ms	640 KB	1
101_largerand_03.in	AC	22 ms	812 KB	1
101_largerand_04.in	AC	19 ms	848 KB	1