问一个算法问题

jssd · 发表于 2012-1-13 12:15:55

在XY坐标上，已知一些点（大于8小于20且都在第一象限，也就是x>0,y>0），求能将这些点包围的面积最小的长方形。
这怎么弄？

NJ8888 · 发表于 2012-1-13 12:21:24

肯定是minX,maxX,minY,maxY

jssd · 发表于 2012-1-13 12:30:08

回复【1楼】NJ8888 NJ8888
肯定是minx,maxx,miny,maxy
-----------------------------------------------------------------------

不一定，你这个没旋转。

aheadlead · 发表于 2012-1-13 13:24:53

你看看计算几何的凸包问题吧

我认为可以先求出凸包再根据每个边去找最小的矩形，不过求凸包就把这题目搞得很复杂，我记得有简单的方法，一下子忘了。

PS 我只是知道有二维凸包这个东西的存在没写过代码可以参考《算法导论》

——————————

其实不用求凸包

我有点理解错误

我认为可以先枚举一对点，使其他的点都在这一对点形成的直线的一边，再找出离直线最远的那个点，剩下的就好办了

当然这个方法对大数据应该不适用

memo1999 · 发表于 2012-1-13 13:56:37

瞎想了下，不知对不：
（1）找到最小X点以及最小Y点，
（2）然后其他点分别与这两点算距离，得到最大距离，两端点分别为A、B，线AB作为对角线；
（3）再分别算其他点到A、B的值，得到一个最大值，假设有另外一点C到A的距离是最大；
（4）连接Ｂ、Ｃ两点，从Ａ向ＢＣ及其延长线做垂线，得到垂点Ｄ；
（5）ABD三点是所求长方形的三个顶点，可求得最后一顶点。

jssd · 发表于 2012-1-13 14:10:34

回复【3楼】aheadlead 高中SB
你看看计算几何的凸包问题吧
我认为可以先求出凸包再根据每个边去找最小的矩形，不过求凸包就把这题目搞得很复杂，我记得有简单的方法，一下子忘了。
ps 我只是知道有二维凸包这个东西的存在没写过代码可以参考《算法导论》
——————————
其实不用求凸包
我有点理解错误
我认为可以先枚举一对点，使其他的点都在这一对点形成的直线的一边，再找出离直线最远的那个点，剩下的就好办了
当然这个方法对大数据应该不适用
-----------------------------------------------------------------------

算了一下，不同的一对点就会产生不一样的长方形。这样算应该是不对的。

jssd · 发表于 2012-1-13 14:23:00

回复【4楼】memo1999
瞎想了下，不知对不：
（1）找到最小x点以及最小y点，
（2）然后其他点分别与这两点算距离，得到最大距离，两端点分别为a、b，线ab作为对角线；
（3）再分别算其他点到a、b的值，得到一个最大值，假设有另外一点c到a的距离是最大；
（4）连接ｂ、ｃ两点，从ａ向ｂｃ及其延长线做垂线，得到垂点ｄ；
（5）abd三点是所求长方形的三个顶点，可求得最后一顶点。

-----------------------------------------------------------------------

好像第三点有问题，是不是应该改成到c到AB的距离最大。
还有第二点，ab线是否真的是对角线呢？

我试一下。谢谢

catx · 发表于 2012-1-13 15:07:33

很容易
方法很多种：

1. 凸包
2. 椭圆拟合
3. 投影法
4. PCA

aheadlead · 发表于 2012-1-13 16:25:18

回复【5楼】jssd 龙
-----------------------------------------------------------------------

所以说要枚举嘛
枚举的时候记一下最小值

nomsg · 发表于 2012-1-13 16:29:23

回复【6楼】jssd 龙
回复【4楼】memo1999
瞎想了下，不知对不：
（1）找到最小x点以及最小y点，
（2）然后其他点分别与这两点算距离，得到最大距离，两端点分别为a、b，线ab作为对角线；
（3）再分别算其他点到a、b的值，得到一个最大值，假设有另外一点c到a的距离是最大；
（4）连接ｂ、ｃ两点，从ａ向ｂｃ及其延长线做垂线，得到垂点ｄ；
（5）abd三点是所求长方形的三个顶点，可求得最后一顶点。
-----------------------------------------------------------------------
好像第三点有问题，是不是应该改成到c到ab的距离最大。
还有第二点，ab线是否真的是对角线呢？
我试一下。谢谢
-----------------------------------------------------------------------
貌似不行，例子如下

(原文件名:未命名.JPG)
A、B、C、D是假设的4个散点，也即矩形ABCD所需要的矩形
若按楼主算法得到的矩形BEGH

我得猜想是：
（1）找出两点间最长的点A、C
（2）线AC作为矩形对角线；
（3）再分别算其他点到AC的值，得到一个最大值，假设有另外一点E到AC的距离是最大；
（4）连接A、E两点，延长AE，过C做AE的垂线，垂足为B；
（5）ABC三点是所求矩形的三个顶点，可求得最后一顶点

（1）（3）费时，不知道对不

aheadlead · 发表于 2012-1-13 16:41:22

回复【6楼】jssd 龙
-----------------------------------------------------------------------

请详细解释
我可能理解不到位
试出了反例

comway · 发表于 2012-1-13 16:57:35

有什么实际意义？

memo1999 · 发表于 2012-1-13 17:16:53

回复【9楼】nomsg
-----------------------------------------------------------------------

按照这个例子算出的对角线也应该是AC或BD啊，你是不是哪里理解错了。

aheadlead · 发表于 2012-1-13 17:22:07

回复【11楼】comway 移动狗
-----------------------------------------------------------------------

莫非USACO整个网站都没有意义了？

问一个算法问题

阿莫论坛20周年了！感谢大家的支持与爱护！！