矩形合并
矩形合并已知n(n>3)个矩形以及每个矩形的四个顶点坐标
n个矩形都在x正半轴和y正半轴内
每两个矩形合并后形成一个完全包含这两个矩形的大矩形
一直合并直到剩余3(或以内)个为止
求最后合并出的3个矩形个顶点坐标
要求是 最后三个矩形面积和最小
不用考虑定点坐标太大问题
代码复杂度 最好 小点。。。。。。。。
所有矩形 完全是 有两条边与x轴平行 有两条边与y轴平行 是所有矩形
伪码 求优化
areaq = MAX;
while ( n > 3 )
{
for (i = 0; i < n-1; i++)
{
for (j = i+1; j < n; j++)
{
aream = area(i+j)-a(i)-a(j);
if(aream<areaq)
{
areaq = aream;
}
}
}
h=i+j;
delete i;
delete j;
add h;
}