给定一个矩阵 N 一排 M 列，由三个值{r，g，b}组成。任务是找到最大三角形的面积，该三角形的一侧平行于y轴，即垂直，且所有三个顶点的颜色都不同。 例如：
null
Input : N = 4, M =5 mat[][] = { r, r, r, r, r, r, r, r, r, g, r, r, r, r, r, b, b, b, b, b, }Output : 10The maximum area of triangle is 10.Triangle coordinates are (0,0) containing r, (1,4) containing g, (3,0) containing b.
![图片[1]-具有不同顶点颜色的三角形的最大面积-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_maximum-area-of-triangle-having-different-vertex-colors.png)
我们知道三角形的面积=1/2*base*height，所以我们需要最大化三角形的基底和高度。由于一边平行于y轴，所以我们可以认为边是三角形的基础。 为了使基最大化，我们可以为每列找到{r，g，b}的第一次和最后一次出现。每列有两组3个值。对于任何列中的基准，一个顶点来自第一个集合，第二个顶点来自第二个集合，因此它们具有不同的值。 要使高度最大化，对于任何作为基准的柱，必须选择第三个顶点，以便该顶点距离柱最远，位于柱的左侧或右侧，其值与其他两个顶点不同。 现在为每列求三角形的最大面积。 以下是该方法的实施情况：
C++
// C++ program to find maximum area of triangle // having different vertex color in a matrix. #include<bits/stdc++.h> using namespace std; #define R 4 #define C 5 // return the color value so that their corresponding // index can be access. int mapcolor( char c) { if (c == 'r' ) return 0; else if (c == 'g' ) return 1; else if (c == 'b' ) return 2; } // Returns the maximum area of triangle from all // the possible triangles double findarea( char mat[R][C], int r, int c, int top[3][C], int bottom[3][C], int left[3], int right[3]) { double ans = ( double )1; // for each column for ( int i = 0; i < c; i++) // for each top vertex for ( int x = 0; x < 3; x++) // for each bottom vertex for ( int y = 0; y < 3; y++) { // finding the third color of // vertex either on right or left. int z = 3 - x - y; // finding area of triangle on left side of column. if (x != y && top[x][i] != INT_MAX && bottom[y][i] != INT_MIN && left[z] != INT_MAX) { ans = max(ans, (( double )1/( double )2) * (bottom[y][i] - top[x][i]) * (i - left[z])); } // finding area of triangle on right side of column. if (x != y && top[x][i] != INT_MAX && bottom[y][i] != INT_MIN && right[z] != INT_MIN) { ans = max(ans, (( double )1/( double )2) * (bottom[y][i] - top[x][i]) * (right[z] - i)); } } return ans; } // Precompute the vertices of top, bottom, left // and right and then computing the maximum area. double maxarea( char mat[R][C], int r, int c) { int left[3], right[3]; int top[3][C], bottom[3][C]; memset (left, INT_MAX, sizeof left); memset (right, INT_MIN, sizeof right); memset (top, INT_MAX, sizeof top); memset (bottom, INT_MIN, sizeof bottom); // finding the r, b, g cells for the left // and right vertices. for ( int i = 0; i < r; i++) { for ( int j = 0; j < c; j++) { left[mapcolor(mat[i][j])] = min(left[mapcolor(mat[i][j])], j); right[mapcolor(mat[i][j])] = max(left[mapcolor(mat[i][j])], j); } } // finsing set of {r, g, b} of top and // bottom for each column. for ( int j = 0; j < c; j++) { for ( int i = 0; i < r; i++) { top[mapcolor(mat[i][j])][j] = min(top[mapcolor(mat[i][j])][j], i); bottom[mapcolor(mat[i][j])][j] = max(bottom[mapcolor(mat[i][j])][j], i); } } return findarea(mat, R, C, top, bottom, left, right); } // Driven Program int main() { char mat[R][C] = { 'r' , 'r' , 'r' , 'r' , 'r' , 'r' , 'r' , 'r' , 'r' , 'g' , 'r' , 'r' , 'r' , 'r' , 'r' , 'b' , 'b' , 'b' , 'b' , 'b' , }; cout << maxarea(mat, R, C) << endl; return 0; } |
Python3
# Python3 program to find the maximum # area of triangle having different # vertex color in a matrix. # Return the color value so that their # corresponding index can be access. def mapcolor(c): if c = = 'r' : return 0 elif c = = 'g' : return 1 elif c = = 'b' : return 2 # Returns the maximum area of triangle # from all the possible triangles def findarea(mat, r, c, top, bottom, left, right): ans = 1 # for each column for i in range ( 0 , c): # for each top vertex for x in range ( 0 , 3 ): # for each bottom vertex for y in range ( 0 , 3 ): # finding the third color of # vertex either on right or left. z = 3 - x - y # finding area of triangle on # left side of column. if (x ! = y and top[x][i] ! = INT_MAX and bottom[y][i] ! = INT_MIN and left[z] ! = INT_MAX): ans = max (ans, 0.5 * (bottom[y][i] - top[x][i]) * (i - left[z])) # finding area of triangle on right side of column. if (x ! = y and top[x][i] ! = INT_MAX and bottom[y][i] ! = INT_MIN and right[z] ! = INT_MIN): ans = max (ans, 0.5 * (bottom[y][i] - top[x][i]) * (right[z] - i)) return ans # Precompute the vertices of top, bottom, left # and right and then computing the maximum area. def maxarea(mat, r, c): left = [ - 1 ] * 3 right = [ 0 ] * 3 top = [[ - 1 for i in range (C)] for j in range ( 3 )] bottom = [[ 0 for i in range (C)] for j in range ( 3 )] # finding the r, b, g cells for # the left and right vertices. for i in range ( 0 , r): for j in range ( 0 , c): left[mapcolor(mat[i][j])] = min (left[mapcolor(mat[i][j])], j) right[mapcolor(mat[i][j])] = max (left[mapcolor(mat[i][j])], j) # finsing set of r, g, b of top # and bottom for each column. for j in range ( 0 , c): for i in range ( 0 , r): top[mapcolor(mat[i][j])][j] = min (top[mapcolor(mat[i][j])][j], i) bottom[mapcolor(mat[i][j])][j] = max (bottom[mapcolor(mat[i][j])][j], i) return int (findarea(mat, R, C, top, bottom, left, right)) # Driver Code if __name__ = = "__main__" : R, C = 4 , 5 mat = [[ 'r' , 'r' , 'r' , 'r' , 'r' ], [ 'r' , 'r' , 'r' , 'r' , 'g' ], [ 'r' , 'r' , 'r' , 'r' , 'r' ], [ 'b' , 'b' , 'b' , 'b' , 'b' ]] INT_MAX, INT_MIN = float ( 'inf' ), float ( '-inf' ) print (maxarea(mat, R, C)) # This code is contributed by Rituraj Jain |
输出：
10
时间复杂性： O（R*C） 辅助空间： O（R+C） 资料来源： http://stackoverflow.com/questions/40078660/maximum-area-of-triangle-having-all-vertices-of-different-color 本文由 Anuj Chauhan（anuj0503） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
