| 题目名称 | 1723. 最小距离和 |
|---|---|
| 输入输出 | space.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 31 |
| 题目来源 |
 cstdio
于2014-10-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：49， 通过率：12.24% | ||||
 葳棠殇 |
100 | 4.693 s | 1.57 MiB | C++ |
 sxysxy |
100 | 16.861 s | 0.57 MiB | C++ |
 Fmuckss |
100 | 22.358 s | 1.84 MiB | C++ |
 Satoshi |
100 | 23.904 s | 0.75 MiB | C++ |
 zhengtn03 |
100 | 24.860 s | 0.81 MiB | C++ |
|
Satoshi |
100 | 26.268 s | 0.72 MiB | C++ |
|
zhengtn03 |
96 | 17.031 s | 0.75 MiB | C++ |
|
zhengtn03 |
96 | 19.252 s | 0.81 MiB | C++ |
|
葳棠殇 |
96 | 23.766 s | 1.63 MiB | C++ |
|
zhengtn03 |
93 | 6.059 s | 0.81 MiB | C++ |
| 本题关联比赛 | |||
| ZLXSCDay1 | |||
| ZLXSCDay1 | |||
| 关于 最小距离和 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
调参大成功...
| ||||
|
不解，为什么我三个三分套三分跑得那么快......
葳棠殇
2016-03-29 17:53
6楼
| ||||
|
写的是二维模拟退火，有注释，貌似比O（n^2）快
| ||||
 cstdio
2014-10-06 10:32
4楼
| ||||
|
回复 @cstdio :
2003年= =，是不是还要考虑下当年的机器速度。所以你给这道题秒了？最后：学OI技术，就到实验找梦迪  Chenyao2333
2014-10-05 21:02
3楼
| ||||
|
回复 @Chenyao2333 :
这是一个悲伤的故事…… 某集训队论文中提到了这道题，然后论文写了半天讲了一个算法，然后，这个算法是O(N^2)的……再然后，作者的代码最大数据要跑55s……所以问题来了，挖掘机技术哪家强？ cstdio
2014-10-05 17:08
2楼
| ||||
|
给神题跪了,Orzzzzzzzzzzzzzzzzzzzzzz
Chenyao2333
2014-10-05 12:06
1楼
| ||||
【题目描述】
平面上有n（3<=n<=10000）个点（坐标为32位有符号整数范围，且点互不重合），要求一条直线，使得所有点到这条直线的距离和最小。
【输入格式】
第一行一个整数n。
接下来n行每行两个整数，是n个点的坐标。
【输出格式】
一行一个实数，即最小距离和，精确到小数点后两位。
【样例输入】
5
8946 3306
6190 9542
1105 6122
5716 1111
2194 5528
【样例输出】
8285.97
【提示】
【来源】
2003集训队作业 金恺
提示：由极限法可证，这样的直线一定过原图的两个点