【想法题系列】逗比三角形

2014年10月29日1,4290

【题目描述】

J是一名OI退役滚粗文化课选手,他十分喜欢做题,尤其是裸题。他现在有一个二维盒子和一些二维三角形,这个盒子拥有无限的高度和L的宽度。而且他的三角形也都是一些锐角三角形或者是直角三角形。现在小J想把这些三角形放入盒子里,由于小Jtxt大神犇那里学会了魔♂法,所以小J的三角形既可以无视盒子边界又可以重叠放置,但是必须有一条边紧贴盒子底面所在的直线。

现在小J想要最大化在盒子中的被三角形覆盖的区域的面积(即三角形间的重叠部分只算一遍),请问这个最大值应该是多少?

【输入格式】

一行一个整数T,代表数据组数。下面T部分,每部分第一行两个整数N,L分别代表三角形数量与盒子的宽度。下面N行每行三个整数ai,bi,ci表示三角形i的三条边长。

【输出格式】

T行,每行一个实数代表盒子内部被三角形覆盖的区域的面积的最大值。

题解

结论:最短边放在x轴上;放置在x轴上的边确定时,最优解满足所有三角形之间的交点在一条平行于x轴的直线上

证明:

将三角形剖分成宽为d的矩形,从高到低排序,那么我们肯定选择前L/d个矩形放在盒子里最优,那么无限剖分矩形后,假设我们选择的最后一个矩形高度是H,那么对于高度大于H的三角形来说,肯定有一个属于该三角形的高度为H的矩形被选择了。那么对于所有高度大于H的三角形来说,高度为H的部分肯定都放在盒子里了,即交点的高度都是H。

有了上面的结论后,显然,三角形越高越容易被选择,所以三角形应该越高越好。

二分交点高度