比赛场次 295
比赛名称 ZLXSCDay1
比赛状态 已结束比赛成绩
开始时间 2016-03-19 08:00:00
结束时间 2016-03-19 12:00:00
开放分组 全部用户
注释介绍 鉴于有许多人周五上晚自习(HZ的一些人),本比赛会重复一次,已经参加过的同学请不要重复参加,题解将会与明天下午给出
题目名称 最小距离和
输入输出 space.in/out
时间限制 5000 ms (5 s)
内存限制 256 MiB
测试点数 31 简单对比
用户 结果 时间 内存 得分
GravatarRapiz AAAATTTAAAAAATTAAAAA
TTTAAAAATTT
62.612 s 0.39 MiB 64

最小距离和

★★★★   输入文件:space.in   输出文件:space.out   简单对比
时间限制:5 s   内存限制:256 MiB

【题目描述】

平面上有n(3<=n<=10000)个点(坐标为32位有符号整数范围,且点互不重合),要求一条直线,使得所有点到这条直线的距离和最小。

【输入格式】

第一行一个整数n。

接下来n行每行两个整数,是n个点的坐标。

【输出格式】

一行一个实数,即最小距离和,精确到小数点后两位。

【样例输入】

5

8946 3306

6190 9542

1105 6122

5716 1111

2194 5528

【样例输出】

8285.97

【提示】

【来源】

2003集训队作业 金恺

提示:由极限法可证,这样的直线一定过原图的两个点