| 题目名称 | 1662. [ZOJ 1450]最小圆覆盖 |
|---|---|
| 输入输出 | minimalcircle.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-06-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：24， 提交：62， 通过率：38.71% | ||||
 神利·代目 |
100 | 0.000 s | 0.00 MiB | C++ |
 ztx |
100 | 0.006 s | 0.29 MiB | C++ |
 _Horizon |
100 | 0.006 s | 0.33 MiB | C++ |
 _Itachi |
100 | 0.007 s | 0.29 MiB | C++ |
 deadpool66 |
100 | 0.007 s | 0.31 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.007 s | 0.32 MiB | C++ |
 mikumikumi |
100 | 0.007 s | 0.32 MiB | C++ |
 一個人的雨 |
100 | 0.007 s | 0.32 MiB | C++ |
 niconicoqaq |
100 | 0.007 s | 0.32 MiB | C++ |
 cstdio |
100 | 0.008 s | 0.32 MiB | C++ |
| 关于 最小圆覆盖 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这是个可以O(n^3)解决的好题。
话说中垂线交点是什么?表示只会用线段中点+法向量+直线求交点来搞 _Itachi
2017-02-28 17:07
2楼
| ||||
|
数据淼，纯暴力可过……
可以拿这个练随机增量啥的…… | ||||
【题目描述】
写一个程序找出覆盖给定点集的最小圆。至多有100个点。
【输入格式】
输入包含至多10组数据。
每组数据的第一行有一个整数N，代表点集中点的数量。
接下来N行是N个点的坐标。坐标的格式为x y，中间由空格隔开。在最后一组数据后有一行只含有一个0.
【输出格式】
对每组输入数据，输出一行空格隔开的三个实数。前两个实数是圆心的x和y坐标，第三个数是圆的半径。
【输入样例】
2
0.0 0.0
3 0
5
0 0
0 1
1 0
1 1
2 2
0
【输出样例】
1.50 0.00 1.50
1.00 1.00 1.41
【提示】
只要你的输出和标准输出不超过0.01，我们就认为你的输出是正确的。
【来源】
Asia 1997, Shanghai (Mainland China)