[APIO2010] 信号覆盖

题目描述

一家电信公司正在北京城搭建一个 GSM 网络。城市里共有 n 个房子需要被 信号覆盖。由于经费的限制,电信公司只能安装一个天线。 这里将每个房子用一个点坐标来表示。为了简化天线的放置,电信公司将会 选择其中的 3 个房子作一个外接圆,然后将天线放在圆的中心,所有位于这个圆 内或者圆的边界上的房子都将被天线的信号所覆盖。 电信公司将会随机选择城市中的 3 个房子来搭建天线,他们想知道在所有可 能放置天线的方案中平均会有多少个房子被信号覆盖。 例如,假设共有 4 个房子 A, B, C, D,它们的位置如下图: ![](https://cdn.luogu.com.cn/upload/pic/4405.png) 如果我们选择ABC或者BCD三个点搭建的外接圆,所有的房子都会被覆盖。 如果我们选择 ACD 或者 ABD,剩下的房子将不会在天线的信号覆盖范围内。因 此平均有(4 + 4 + 3 + 3) / 4 = 3.50 个房子被信号覆盖。 给定所有房子的位置,你的任务是计算平均有多少个房子被信号覆盖。假定 每一个房子都有一个二维的整数坐标,并且保证任何三个房子都不在同一条直线 上,任何四个房子都不在同一个圆上。

输入输出格式

输入格式


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

输出格式


输出文件包含一个实数,表示平均有多少个房子被信号所覆盖,需保证输出 结果与精确值的绝对误差不超过 0.01。

输入输出样例

输入样例 #1

4
0 2 
4 4 
0 0 
2 0

输出样例 #1

3.500 

说明

【样例说明】 3.5, 3.50, 3.500, … 中的任何一个输出均为正确。此外,3.49, 3.51, 3.499999,…等也都是可被接受的输出。 【数据范围】 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。