所有顶点颜色不同的三角形的最大面积
Maximum area of triangle having all vertices of different color
笛卡尔平面中从 (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
谁能告诉我解决这个问题的方法吗？
三角形的面积是1/2 * base * height。所以如果三角形的一侧平行于
x 轴，则三角形的底部由同一行上的两种颜色形成（尽可能分开），第三种颜色应位于距离底部最远的行上。因此，您可以预处理数据以找到：
- 每种颜色的最顶部和最底部的行
- 每行每种颜色的最左边和最右边的列
然后对于每一行，你有十二种可能形成三角形，例如
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)时间内解决，其中大部分时间花在了预处理上。
笛卡尔平面中从 (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
谁能告诉我解决这个问题的方法吗？
三角形的面积是1/2 * base * height。所以如果三角形的一侧平行于
x 轴，则三角形的底部由同一行上的两种颜色形成（尽可能分开），第三种颜色应位于距离底部最远的行上。因此，您可以预处理数据以找到：
- 每种颜色的最顶部和最底部的行
- 每行每种颜色的最左边和最右边的列
然后对于每一行，你有十二种可能形成三角形，例如
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)时间内解决，其中大部分时间花在了预处理上。