a284. APIO2010 3.信号覆盖 - 高中生程式解題系統

內容

一家电信公司正在北京城搭建一个GSM网络。城市里共有n个房子需要被信号覆盖。由于经费的限制，电信公司只能安装一个天线。这里将每个房子用一个点坐标来表示。为了简化天线的放置，电信公司将会选择其中的3个房子作一个外接圆，然后将天线放在圆的中心，所有位于这个圆内或者圆的边界上的房子都将被天线的信号所覆盖。电信公司将会随机选择城市中的3个房子来搭建天线，他们想知道在所有可能放置天线的方案中平均会有多少个房子被信号覆盖。例如，假设共有4个房子A, B, C, D，它们的位置如下图：

如果我们选择ABC或者BCD三个点搭建的外接圆，所有的房子都会被覆盖。如果我们选择ACD或者ABD，剩下的房子将不会在天线的信号覆盖范围内。因此平均有(4 + 4 + 3 + 3) / 4 = 3.50个房子被信号覆盖。给定所有房子的位置，你的任务是计算平均有多少个房子被信号覆盖。假定每一个房子都有一个二维的整数坐标，并且保证任何三个房子都不在同一条直线上，任何四个房子都不在同一个圆上。

輸入說明

输入第一行包含一个正整数n, 表示房子的总数。接下来有n行，分别表示每一个房子的位置。对于i = 1, 2, .., n, 第i个房子的坐标用一对整数xi和yi来表示，中间用空格隔开。

輸出說明

输出文件包含一个实数，表示平均有多少个房子被信号所覆盖，输出结果保留小数点后6位。

範例輸入 #1

範例輸出 #1

3.500000

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 2.0s , <1K
公開測資點#1 (10%): 2.0s , <1K
公開測資點#2 (10%): 2.0s , <1K
公開測資點#3 (10%): 2.0s , <1M
公開測資點#4 (10%): 2.0s , <1M
公開測資點#5 (10%): 2.0s , <1M
公開測資點#6 (10%): 2.0s , <1M
公開測資點#7 (10%): 2.0s , <1M
公開測資點#8 (10%): 2.0s , <1M
公開測資點#9 (10%): 2.0s , <1M

提示：

100%的数据保证，对于i = 1, 2, .., n, 第i个房子的坐标(xi, yi)为整数且 –1,000,000 ≤ xi, yi ≤ 1,000,000. 任何三个房子不在同一条直线上，任何四个房子不在同一个圆上；

40%的数据，n ≤ 100；
70%的数据，n ≤ 500；
100%的数据，3 ≤ n ≤ 1,500。

※感谢morris1028提供图片！

標籤:

出處:

APIO 2010 第三题 [管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」