[APIO2010]signaling 信号覆盖

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 signaling.in 输出文件 signaling.out

【题目描述】

【输入格式】

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

【输出格式】

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

【样例输入】 


4





0 2





4 4





0 0





2 0

【样例输出】 

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。



【来源】

[Apio2010]signaling 信号覆盖

耒阳大视野 1913