Marathon

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 경쟁자의 완주 시간이 [a_i, b_i]에서 균등분포를 따를 때, 모든 경쟁자를 이길 확률이 50퍼센트가 되는 에릭의 최대 완주 시간을 구한다.

난이도: 보통10점 중 6점
유형: 확률, 이분 탐색, 수학
정답자: 아직 제출이 없습니다

문제

Erik wants to run a marathon. Most of all, he wants to win the race. To plan his training, he has looked up how the other contestants performed in previous races and made a model to predict his chances of winning. The finishing time for each contestant is distributed uniformly at random in an interval $\[a\_i, b\_i]$ . What is the largest finishing time Erik can have while still having a $50\\%$ change of winning?

입력

The first line contains an integer $1 \leq N \leq 10^5$ , the number of other contestants. Then follows $N$ lines, each with two floating point values $0 \leq a\_i \leq 10^5$ and $a\_i \le b\_i \leq 10^5$ with at exactly one decimal place, the start and end time in seconds for their finishing time.

출력

A single floating point number, the largest finishing time in seconds that Erik needs to have a $50\\%$ chance of winning. The answer must be with a relative or absolute error of at most $10^{-6}$ .

예제2

예제 1
입력
```
1
1.0 3.0
```
예상 출력
```
2.0
```

예제 2

입력

3
0.0 10.0
3.5 6.7
2.2 4.5

예상 출력

2.883937700856755