Horisont

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

요약

원점 둘레의 상자들이 놓인 정수 격자에서 전체 지평선 원 중 상자에 가려지지 않고 보이는 부분의 비율을 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Juku seisab lõpmatul ruudulisel paberil koordinaatide alguspunktis $(0;0)$ . Osadele ruutudele on asetatud kastid, mis varjavad nähtavust. Leida, kui suur osa horisondist on nähtav.

입력

Tekstifaili esimesel real on kastide arv $N$ ( $0 \le N \le 100\\,000$ ) ja järgmisel $N$ igaühel kaks täisarvu $X$ ja $Y$ ( $|X| \le 10^9$ , $|Y| \le 10^9$ ): ühe kasti vasaku alumise nurga koordinaadid. Võib eeldada, et mingid kaks kasti pole samas ruudus.

출력

Tekstifaili ainsale reale väljastada reaalarv $p$ ( $0 \le p \le 1$ ), mis näitab horisondi Jukule nähtava osa suhet kogu horisonti (täisringi). Väljastatud vastus ei tohi täpsest väärtusest erineda rohkem kui $0{,}00001$ võrra.

예제2

예제 1
입력
```
1
0 0
```
예상 출력
```
0.75
```

예제 2

입력

7
1 1
-2 -2
-4 -2
-4 -1
-4 0
-4 1
-2 1

예상 출력

0.545167235300867