发个题目看谁会做 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

发个题目看谁会做

发个题目看谁会做# JobHunting - 待字闺中

M*a2013-09-10 07:09

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*m2013-09-10 07:09

2 楼

难！不共线那个条件怎么也想不出来怎么用。

d*52013-09-10 07:09

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*m2013-09-10 07:09

4 楼

3不一定符合，1可以有n个解吧。

【在 d****5 的大作中提到】

: 1. 先找到两点，其他的点都在其连线的一侧
: 2. 计算其他点与这两点共圆的半径
: 3. 取半径第n+1小的即可

M*a2013-09-10 07:09

5 楼

能不能证明下？
但是感觉这么找总归能找到一个，但是为什么就是n+1半径哪个？

【在 d****5 的大作中提到】

: 1. 先找到两点，其他的点都在其连线的一侧
: 2. 计算其他点与这两点共圆的半径
: 3. 取半径第n+1小的即可

d*52013-09-10 07:09

6 楼

嗯，把2改成圆心的位置排序就可以了。从没有点的那侧开始数第n+1个。
1是可以有很多解，所以这题也有很多解。
BTW：1用到了共线的条件，3用到了共圆的条件

【在 a********m 的大作中提到】

: 3不一定符合，1可以有n个解吧。

e*82013-09-10 07:09

7 楼

这个其实是个智力题吧-_-bbb
以前在cut-the-knot上见过。。。关键就是包含若干个点的最小的圆，一定是有三个点
恰好在圆上的。那些找最小的enclosing个k个点的算法一般都会用到这个条件。
http://www.cut-the-knot.org/Generalization/scircles.shtml

a*m2013-09-10 07:09

8 楼

还是觉得3不一定能找到，除非你能证明。

【在 d****5 的大作中提到】

: 嗯，把2改成圆心的位置排序就可以了。从没有点的那侧开始数第n+1个。
: 1是可以有很多解，所以这题也有很多解。
: BTW：1用到了共线的条件，3用到了共圆的条件

g*e2013-09-10 07:09

9 楼

厉害

【在 d****5 的大作中提到】

: 1. 先找到两点，其他的点都在其连线的一侧
: 2. 计算其他点与这两点共圆的半径
: 3. 取半径第n+1小的即可

d*52013-09-10 07:09

10 楼

找不到什么？圆心都已经在第2步算出来了啊。

【在 a********m 的大作中提到】

: 还是觉得3不一定能找到，除非你能证明。

M*a2013-09-10 07:09

11 楼

好像对的，我来证明
1. 两个点确定之后，每一个剩下的点都能和这两个点形成一个圆，而且这些圆半径都
不一样，因为没有四个点共圆，所以有2n+1个圆，也就是2n+1个不同的半径。
2. 所以找第n+1大的半径的圆就是，半径比他小的点肯定在里面，大的在外面
不错
类似题目比如找最大圆包括所有点基本也这么做

【在 a********m 的大作中提到】

: 还是觉得3不一定能找到，除非你能证明。

g*y2013-09-10 07:09

12 楼

好像没论证步骤 1的重要性. 不过这个只要注意道圆心必在步骤 1给出的两点的垂直
中分线上就能证出

【在 M*******a 的大作中提到】

: 好像对的，我来证明
: 1. 两个点确定之后，每一个剩下的点都能和这两个点形成一个圆，而且这些圆半径都
: 不一样，因为没有四个点共圆，所以有2n+1个圆，也就是2n+1个不同的半径。
: 2. 所以找第n+1大的半径的圆就是，半径比他小的点肯定在里面，大的在外面
: 不错
: 类似题目比如找最大圆包括所有点基本也这么做

d*52013-09-10 07:09

13 楼

用半径是不成立的，过两点可以做两个同样半径的不同的圆。。。
所以我后面改成用圆心的位置。。。

【在 M*******a 的大作中提到】

l*i2013-09-10 07:09

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*a2013-09-10 07:09

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*a2013-09-10 07:09

16 楼

半径对的应该，过两点可以做两个且仅有两个同样半径的圆（如果正好是直径就只有一
个），但是我们现在就考虑一面的圆，就是所有其他点的所在那边的那个圆
而且如果有另外一个圆也经过这两点，也是同一边，并且半径更大，弧上的所有点都在
小圆弧的外面，所以用半径排序对的

【在 d****5 的大作中提到】

: 用半径是不成立的，过两点可以做两个同样半径的不同的圆。。。
: 所以我后面改成用圆心的位置。。。

a*m2013-09-10 07:09

17 楼

错。你再想想吧。

【在 M*******a 的大作中提到】

: 半径对的应该，过两点可以做两个且仅有两个同样半径的圆（如果正好是直径就只有一
: 个），但是我们现在就考虑一面的圆，就是所有其他点的所在那边的那个圆
: 而且如果有另外一个圆也经过这两点，也是同一边，并且半径更大，弧上的所有点都在
: 小圆弧的外面，所以用半径排序对的

M*a2013-09-10 07:09

18 楼

错哪里？

【在 a********m 的大作中提到】

: 错。你再想想吧。

M*a2013-09-10 07:09

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*n2013-09-10 07:09

20 楼

确保最后那个圆不是半径无穷大吧。

【在 a********m 的大作中提到】

: 难！不共线那个条件怎么也想不出来怎么用。

d*52013-09-10 07:09

21 楼

按照半径就要取点4所在圆，显然3，5均在该圆外面

【在 M*******a 的大作中提到】

: 错哪里？

M*a2013-09-10 07:09

22 楼

发信站: BBS 未名空间站 (您看下我前面的终极证明对不对？

【在 d****5 的大作中提到】

: 按照半径就要取点4所在圆，显然3，5均在该圆外面

d*n2013-09-10 07:09

23 楼

不对吧，和圆心位置也有关系。

【在 M*******a 的大作中提到】

d*n2013-09-10 07:09

24 楼

yes, and some heuristic can be used to find the circle more quickly

we
n

【在 l***i 的大作中提到】

d*n2013-09-10 07:09

25 楼

好图！

【在 d****5 的大作中提到】

: 按照半径就要取点4所在圆，显然3，5均在该圆外面

d*n2013-09-10 07:09

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*l2013-09-10 07:09

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*52013-09-10 07:09

28 楼

你这个方法没错，不过要判断大小弧，不如直接比较圆心位置。

一的

【在 M*******a 的大作中提到】

M*a2013-09-10 07:09

29 楼

符合阿，ab是直径，另一个点在半圆上不可能共线

【在 f****l 的大作中提到】

: 3(c)符不符合没有三点共线的要求？
:
: 一的

M*a2013-09-10 07:09

30 楼

我老就这意思啊，大小弧就是这么判断阿

【在 d****5 的大作中提到】

: 你这个方法没错，不过要判断大小弧，不如直接比较圆心位置。
:
: 一的

M*a2013-09-10 07:09

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)