algorithm - 所有顶点颜色不同的三角形的最大面积

Question

笛卡尔平面中从 (0,0) 到 (R,C) 的点的颜色为 r、g 或 b。使用这些点制作一个三角形，这样 -

a) All three vertices are of different colors.
b) At least one side of triangle is parallel to either of the axes.
c) Area of the triangle is maximum possible.

输出最大可能的区域。约束条件:1<=R<=1000 , 1<=C<=1000

有人可以告诉我解决这个问题的方法吗？

Answer 1

三角形的面积是1/2 * base * height。所以如果三角形的一侧平行于
x 轴，则三角形的底部由同一行上的两种颜色形成(尽可能分开)，第三种颜色应位于距离底部最远的行上。因此，您可以预处理数据以找到:

1. 每种颜色的最顶行和最底行
2. 每行每种颜色的最左边和最右边的列

然后对于每一行，您有十二种可能形成三角形，例如

left-most-red, right-most-blue, top-most green
left-most-red, right-most-blue, bottom-most green
left-most-red, right-most-green, top-most blue
...

当然，对于单边平行于y轴的三角形，也有相应的处理。

因此，问题可以在 O(R*C) 时间内解决，其中大部分时间花在了预处理上。