各位看看一道算法题

gyCai · 发表于 2010-3-29 00:46

有2堆2维点集，人一眼就能看出它们是2堆。
在其中某一堆里选择2个点连成一条直线AB；过另一堆里的某个点作一条直线C，C必须平行于AB，使得
1.两个平现线之间的空白处不含有2堆点里的任何一点；
2.这个空白尽可能大.
如何选取这3个点

不会游泳鱼 · 发表于 2010-3-29 09:39

是不是这样:

寻找A, B, C, 使得d最大?

六月飞霜 · 发表于 2010-3-29 20:38

那不是变成了求一堆的点到二堆边线最短距离集的最大值？

gyCai · 发表于 2010-3-29 20:58

应该不对，这个解无法满足要求。
觉得应该把这些点都变成凸形处理。在两堆中任意选取3个点作三角形，如果这个三角形中间存在其它点，则去掉这些其它的点，然后再选取1个点与三角形的两个顶点作三角形，再重复判断是否存在中间点的步骤，如此下去，最后两堆点应该是形成两个圈，然后再找符合条件的点...

efen · 发表于 2010-3-31 23:52

LSSS有图怎样画的

DieIng · 发表于 2010-4-2 17:01

先对其中一堆求凸包O(nlgn)。。然后枚举凸包相邻的两点做AB，O(n)，在另一堆枚举点作为C，求出最优，O(n),总复杂度O(n^2)。。
PS:这个是暴力的做法，感觉应该有优于O(n^2)的。。。

		自动登录	找回密码
密码			加入后院