4574 . A4. 白紙 (Paper)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

取一素紙，以墨滴之。今已滴落之墨，盡知其座標，皆為格子點，且墨之直徑皆為一單位，試求下一滴墨（未必滴於格子點，直徑也一單位）隨機滴落時與任何已滴之墨重疊之機率為何？

Input Format

第一行為 墨滴數 紙寬 紙高

接著若干行為各墨滴之座標 $x$ $y$ （$0 \leq x \leq$ 紙寬，$0 \leq y \leq$ 紙高）

紙張大小不超出 $200 \times 200$

墨滴數 $\leq 20000$

Output Format

重疊的機率（$0 \leq$ 答案 $\leq 1）$

※ 因為 cjtsai 很好心給你寬容一下，輸出的答案與真正的答案絕對誤差在 $10 ^ {-6}$ 內皆視為正確

※ 請將 $\pi$ 視為 3.141592653589793，$\sqrt 3$ 視為 1.732050807568877

Sample Input 1

3 5 4
2 2
1 1
2 1

Sample Output 1

0.34201069

Hints

Sample 1:

Sample 2:

Problem Source

TopCoder

AaW
學弟電爛我了

User's AC Ratio

50.0% (1/2)

Tags

學術上機考 112 學年度

Problem Setter

Created by 晴

Subtasks

No. Testdata Range Constraints Score
1 0 無墨於此，不乎易耶？ 1
2 1~4 無墨滴在紙之邊緣，墨滴之間必有一單位之隙 24
3 5~9 墨滴之間必有一單位之隙 25
4 10~19 無特別限制也 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 3
6 1000 262144 65536 3
7 1000 262144 65536 3
8 1000 262144 65536 3
9 1000 262144 65536 3
10 1000 262144 65536 4
11 1000 262144 65536 4
12 1000 262144 65536 4
13 1000 262144 65536 4
14 1000 262144 65536 4
15 1000 262144 65536 4
16 1000 262144 65536 4
17 1000 262144 65536 4
18 1000 262144 65536 4
19 1000 262144 65536 4
Submit
Back to Top