M*******a
发帖数: 1633 | 1 Given 2*n + 3 points in 2d space, with no 3 points col-linear and no 4
points lying on a circle, device an algorithm that will find a circle that
contains n points inside it, n outside it and 3 on it. |
a********m
发帖数: 15480 | |
d****5
发帖数: 202 | 3 1. 先找到两点，其他的点都在其连线的一侧
2. 计算其他点与这两点共圆的半径
3. 取半径第n+1小的即可
【在 M*******a 的大作中提到】
: Given 2*n + 3 points in 2d space, with no 3 points col-linear and no 4
: points lying on a circle, device an algorithm that will find a circle that
: contains n points inside it, n outside it and 3 on it.
|
a********m
发帖数: 15480 | 4 3不一定符合，1可以有n个解吧。
【在 d****5 的大作中提到】
: 1. 先找到两点，其他的点都在其连线的一侧
: 2. 计算其他点与这两点共圆的半径
: 3. 取半径第n+1小的即可
|
M*******a
发帖数: 1633 | 5 能不能证明下？
但是感觉这么找总归能找到一个，但是为什么就是n+1半径哪个？
【在 d****5 的大作中提到】
: 1. 先找到两点，其他的点都在其连线的一侧
: 2. 计算其他点与这两点共圆的半径
: 3. 取半径第n+1小的即可
|
d****5
发帖数: 202 | 6 嗯，把2改成圆心的位置排序就可以了。从没有点的那侧开始数第n+1个。
1是可以有很多解，所以这题也有很多解。
BTW：1用到了共线的条件，3用到了共圆的条件
【在 a********m 的大作中提到】
: 3不一定符合，1可以有n个解吧。
|
e*******8
发帖数: 94 | 7 这个其实是个智力题吧-_-bbb
以前在cut-the-knot上见过。。。关键就是包含若干个点的最小的圆，一定是有三个点
恰好在圆上的。那些找最小的enclosing个k个点的算法一般都会用到这个条件。
http://www.cut-the-knot.org/Generalization/scircles.shtml |
a********m
发帖数: 15480 | 8 还是觉得3不一定能找到，除非你能证明。
【在 d****5 的大作中提到】
: 嗯，把2改成圆心的位置排序就可以了。从没有点的那侧开始数第n+1个。
: 1是可以有很多解，所以这题也有很多解。
: BTW：1用到了共线的条件，3用到了共圆的条件
|
g*********e
发帖数: 14401 | 9
厉害
【在 d****5 的大作中提到】
: 1. 先找到两点，其他的点都在其连线的一侧
: 2. 计算其他点与这两点共圆的半径
: 3. 取半径第n+1小的即可
|
d****5
发帖数: 202 | 10 找不到什么？圆心都已经在第2步算出来了啊。
【在 a********m 的大作中提到】
: 还是觉得3不一定能找到，除非你能证明。
|
|
|
M*******a
发帖数: 1633 | 11 好像对的，我来证明
1. 两个点确定之后，每一个剩下的点都能和这两个点形成一个圆，而且这些圆半径都
不一样，因为没有四个点共圆，所以有2n+1个圆，也就是2n+1个不同的半径。
2. 所以找第n+1大的半径的圆就是，半径比他小的点肯定在里面，大的在外面
不错
类似题目比如找最大圆包括所有点基本也这么做
【在 a********m 的大作中提到】
: 还是觉得3不一定能找到，除非你能证明。
|
g**y
发帖数: 46 | 12 好像没论证 步骤 1的重要性. 不过这个只要注意道圆心必在 步骤 1给出的两点的垂直
中分线上就能证出
【在 M*******a 的大作中提到】
: 好像对的，我来证明
: 1. 两个点确定之后，每一个剩下的点都能和这两个点形成一个圆，而且这些圆半径都
: 不一样，因为没有四个点共圆，所以有2n+1个圆，也就是2n+1个不同的半径。
: 2. 所以找第n+1大的半径的圆就是，半径比他小的点肯定在里面，大的在外面
: 不错
: 类似题目比如找最大圆包括所有点基本也这么做
|
d****5
发帖数: 202 | 13 用半径是不成立的，过两点可以做两个同样半径的不同的圆。。。
所以我后面改成用圆心的位置。。。
【在 M*******a 的大作中提到】
: 好像对的，我来证明
: 1. 两个点确定之后，每一个剩下的点都能和这两个点形成一个圆，而且这些圆半径都
: 不一样，因为没有四个点共圆，所以有2n+1个圆，也就是2n+1个不同的半径。
: 2. 所以找第n+1大的半径的圆就是，半径比他小的点肯定在里面，大的在外面
: 不错
: 类似题目比如找最大圆包括所有点基本也这么做
|
l***i
发帖数: 1309 | 14 if you do not care about time complexity, try all triples of points, and we
know 3 points defines a circle, then use that circle to see whether it has n
points inside and n points outside.
time complexity: n^3 choices for a circle, and to check a circle valid or
not takes O(n) time, total O(n^4). |
M*******a
发帖数: 1633 | 15 这种brute force就不要说了，本版的人都知道的
we
n
【在 l***i 的大作中提到】
: if you do not care about time complexity, try all triples of points, and we
: know 3 points defines a circle, then use that circle to see whether it has n
: points inside and n points outside.
: time complexity: n^3 choices for a circle, and to check a circle valid or
: not takes O(n) time, total O(n^4).
|
M*******a
发帖数: 1633 | 16 半径对的应该，过两点可以做两个且仅有两个同样半径的圆（如果正好是直径就只有一
个），但是我们现在就考虑一面的圆，就是所有其他点的所在那边的那个圆
而且如果有另外一个圆也经过这两点，也是同一边，并且半径更大，弧上的所有点都在
小圆弧的外面，所以用半径排序对的
【在 d****5 的大作中提到】
: 用半径是不成立的，过两点可以做两个同样半径的不同的圆。。。
: 所以我后面改成用圆心的位置。。。
|
a********m
发帖数: 15480 | 17 错。你再想想吧。
【在 M*******a 的大作中提到】
: 半径对的应该，过两点可以做两个且仅有两个同样半径的圆（如果正好是直径就只有一
: 个），但是我们现在就考虑一面的圆，就是所有其他点的所在那边的那个圆
: 而且如果有另外一个圆也经过这两点，也是同一边，并且半径更大，弧上的所有点都在
: 小圆弧的外面，所以用半径排序对的
|
M*******a
发帖数: 1633 | 18 错哪里？
【在 a********m 的大作中提到】
: 错。你再想想吧。
|
M*******a
发帖数: 1633 | 19 好了我老来终极证明一下
1. 找两个点(ab)使得其他剩下的点ci(i = 1, 2, 3, ... 2n+1)都在两点连线的同一边
，这应该有o(n)的做法，并且结果肯定并不唯一，所以本题显然有很多解
2. 对于剩下的2n+1个ci点，根据条件没有三点共线并且没有四点共圆，我们可以找出
2n+1个不同的圆Oi通过a b和ci点，我们分别求出这些圆的半径Ri，这些Ri也都是唯一的
3. 对于每个圆Oi，a-ci-b点所在的弧又可以分为下述情况
a) 弧a-ci-b是圆Oi弧的小半弧
b) 弧a-ci-b是圆Oi弧的大半弧
c) 弧a-ci-b是圆Oi弧的半圆，也就是ab正好是Oi的直径，这种圆至多只能有一个
对于情况a)，如果Ri1 > Ri2，则弧a-ci1-b在弧a-ci2-b的内部
对于情况b)，如果Ri1 > Ri2，则弧a-ci2-b在弧a-ci1-b的内部
所以我们这样排序得到一个2n+1的半径序列
情况a)的圆按照半径递减排序
c)的圆，如果有的话
情况b)的圆按照半径递增排序
该序列的中位数就是我们找的圆的半径
证毕 |
l*n
发帖数: 529 | 20 确保最后那个圆不是半径无穷大吧。
【在 a********m 的大作中提到】
: 难！不共线那个条件怎么也想不出来怎么用。
|
|
|
d****5
发帖数: 202 | 21 按照半径就要取点4所在圆，显然3，5均在该圆外面
【在 M*******a 的大作中提到】
: 错哪里？
|
M*******a
发帖数: 1633 | 22 发信站: BBS 未名空间站 (您看下我前面的终极证明对不对？
【在 d****5 的大作中提到】
: 按照半径就要取点4所在圆，显然3，5均在该圆外面
|
d*******n
发帖数: 124 | 23 不对吧，和圆心位置也有关系。
【在 M*******a 的大作中提到】
: 好像对的，我来证明
: 1. 两个点确定之后，每一个剩下的点都能和这两个点形成一个圆，而且这些圆半径都
: 不一样，因为没有四个点共圆，所以有2n+1个圆，也就是2n+1个不同的半径。
: 2. 所以找第n+1大的半径的圆就是，半径比他小的点肯定在里面，大的在外面
: 不错
: 类似题目比如找最大圆包括所有点基本也这么做
|
d*******n
发帖数: 124 | 24 yes, and some heuristic can be used to find the circle more quickly
we
n
【在 l***i 的大作中提到】
: if you do not care about time complexity, try all triples of points, and we
: know 3 points defines a circle, then use that circle to see whether it has n
: points inside and n points outside.
: time complexity: n^3 choices for a circle, and to check a circle valid or
: not takes O(n) time, total O(n^4).
|
d*******n
发帖数: 124 | 25 好图！
【在 d****5 的大作中提到】
: 按照半径就要取点4所在圆，显然3，5均在该圆外面
|
d*******n
发帖数: 124 | 26 我来分享一个算法：
1. 先求出包含所有点的mbb,min bounding box. 组合C(2,n)~O(n^2) time.
2. 求mbb上所有点的平均x,y.得到中心点x0,y0.
3. 将所有点按照距离中心点的距离排序。O(nlgn )
4. 从最中心的位置开始每次找三个点画圆，并判断。得到结果即返回。O(n^4)
【在 d*******n 的大作中提到】
: 好图！
|
f****l
发帖数: 8042 | 27 3(c)符不符合没有三点共线的要求？
一的
【在 M*******a 的大作中提到】
: 好了我老来终极证明一下
: 1. 找两个点(ab)使得其他剩下的点ci(i = 1, 2, 3, ... 2n+1)都在两点连线的同一边
: ，这应该有o(n)的做法，并且结果肯定并不唯一，所以本题显然有很多解
: 2. 对于剩下的2n+1个ci点，根据条件没有三点共线并且没有四点共圆，我们可以找出
: 2n+1个不同的圆Oi通过a b和ci点，我们分别求出这些圆的半径Ri，这些Ri也都是唯一的
: 3. 对于每个圆Oi，a-ci-b点所在的弧又可以分为下述情况
: a) 弧a-ci-b是圆Oi弧的小半弧
: b) 弧a-ci-b是圆Oi弧的大半弧
: c) 弧a-ci-b是圆Oi弧的半圆，也就是ab正好是Oi的直径，这种圆至多只能有一个
: 对于情况a)，如果Ri1 > Ri2，则弧a-ci1-b在弧a-ci2-b的内部
|
d****5
发帖数: 202 | 28 你这个方法没错，不过要判断大小弧，不如直接比较圆心位置。
一的
【在 M*******a 的大作中提到】
: 好了我老来终极证明一下
: 1. 找两个点(ab)使得其他剩下的点ci(i = 1, 2, 3, ... 2n+1)都在两点连线的同一边
: ，这应该有o(n)的做法，并且结果肯定并不唯一，所以本题显然有很多解
: 2. 对于剩下的2n+1个ci点，根据条件没有三点共线并且没有四点共圆，我们可以找出
: 2n+1个不同的圆Oi通过a b和ci点，我们分别求出这些圆的半径Ri，这些Ri也都是唯一的
: 3. 对于每个圆Oi，a-ci-b点所在的弧又可以分为下述情况
: a) 弧a-ci-b是圆Oi弧的小半弧
: b) 弧a-ci-b是圆Oi弧的大半弧
: c) 弧a-ci-b是圆Oi弧的半圆，也就是ab正好是Oi的直径，这种圆至多只能有一个
: 对于情况a)，如果Ri1 > Ri2，则弧a-ci1-b在弧a-ci2-b的内部
|
M*******a
发帖数: 1633 | 29 符合阿，ab是直径，另一个点在半圆上不可能共线
【在 f****l 的大作中提到】
: 3(c)符不符合没有三点共线的要求？
:
: 一的
|
M*******a
发帖数: 1633 | 30 我老就这意思啊，大小弧就是这么判断阿
【在 d****5 的大作中提到】
: 你这个方法没错，不过要判断大小弧，不如直接比较圆心位置。
:
: 一的
|
|
|
M*******a
发帖数: 1633 | 31 o(n^4)...
往上看o(nlogn)的
【在 d*******n 的大作中提到】
: 我来分享一个算法：
: 1. 先求出包含所有点的mbb,min bounding box. 组合C(2,n)~O(n^2) time.
: 2. 求mbb上所有点的平均x,y.得到中心点x0,y0.
: 3. 将所有点按照距离中心点的距离排序。O(nlgn )
: 4. 从最中心的位置开始每次找三个点画圆，并判断。得到结果即返回。O(n^4)
|
