서로 다른 정점 색상을 갖는 삼각형의 최대 면적
행렬이 주어지면 N 행과 중 열은 세 개의 값 {r g b}으로 구성됩니다. 과제는 한쪽 변이 y축과 평행한, 즉 수직이고 세 꼭지점의 색상이 모두 다른 가장 큰 삼각형의 면적을 찾는 것입니다.
예:
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 : 10
The maximum area of triangle is 10.
Triangle coordinates are (00) containing r (14) containing g (30) containing b.
우리는 삼각형의 면적 = 1/2 * 밑변 * 높이를 알고 있으므로 삼각형의 밑변과 높이를 최대화해야 합니다. 한 변은 y축과 평행하므로 그 변을 삼각형의 밑변으로 간주할 수 있습니다.
기준을 최대화하기 위해 각 열에 대해 {r g b}의 첫 번째 및 마지막 발생을 찾을 수 있습니다. 따라서 각 열에 대해 3개의 값으로 구성된 두 세트가 있습니다. 모든 열의 기본에 대해 하나의 꼭지점은 첫 번째 세트에서 나오고 두 번째 꼭지점은 두 번째 세트에서 나오므로 서로 다른 값을 갖습니다.
기본 기둥의 높이를 최대화하려면 꼭지점이 다른 두 꼭지점과 다른 값을 갖는 기둥의 왼쪽 또는 오른쪽 기둥에서 가장 멀리 떨어져 있어야 하는 세 번째 꼭지점을 선택해야 합니다.
이제 각 열에 대해 삼각형의 최대 면적을 찾으십시오.
다음은 이 접근 방식의 구현입니다.
C++Java// C++ program to find maximum area of triangle // having different vertex color in a matrix. #includeusing 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 ); } } // finding 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 ; } Python3import java.util.Arrays ; public class Main { static int R = 4 ; static int C = 5 ; static char [][] mat = { { 'r' 'r' 'r' 'r' 'r' } { 'r' 'r' 'r' 'r' 'g' } { 'r' 'r' 'r' 'r' 'r' } { 'b' 'b' 'b' 'b' 'b' } }; public static void main ( String [] args ) { System . out . println ( maxArea ( mat R C )); } // Returns the color value so that their corresponding index can be accessed. static int mapColor ( char c ) { if ( c == 'r' ) return 0 ; else if ( c == 'g' ) return 1 ; else if ( c == 'b' ) return 2 ; else return - 1 ; } // Returns the maximum area of triangle from all the possible triangles static double findArea ( char [][] mat int r int c int [][] top int [][] bottom int [] left int [] right ) { double ans = 10 ; // 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 ] != Integer . MAX_VALUE && bottom [ y ][ i ] != Integer . MIN_VALUE && left [ z ] != Integer . MAX_VALUE ) { ans = Math . 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 && top [ x ][ i ] != Integer . MAX_VALUE && bottom [ y ][ i ] != Integer . MIN_VALUE && right [ z ] != Integer . MIN_VALUE ) { ans = Math . 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. static double maxArea ( char [][] mat int r int c ) { int [] left = new int [ 3 ] ; Arrays . fill ( left Integer . MAX_VALUE ); int [] right = new int [ 3 ] ; Arrays . fill ( right Integer . MIN_VALUE ); int [][] top = new int [ 3 ][ c ] ; for ( int [] row : top ) Arrays . fill ( row Integer . MAX_VALUE ); int [][] bottom = new int [ 3 ][ c ] ; for ( int [] row : bottom ) Arrays . fill ( row Integer . MIN_VALUE ); // 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 ++ ) { int color = mapColor ( mat [ i ][ j ] ); left [ color ] = Math . min ( left [ color ] j ); right [ color ] = Math . max ( right [ color ] j ); } } // Finding 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 ++ ) { int color = mapColor ( mat [ i ][ j ] ); top [ color ][ j ] = Math . min ( top [ color ][ j ] i ); bottom [ color ][ j ] = Math . max ( bottom [ color ][ j ] i ); } } return findArea ( mat r c top bottom left right ); } }C## 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 ) # finding 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 JainJavaScript// C# program to find maximum area of triangle // having different vertex color in a matrix. using System ; class MainClass { const int R = 4 ; const int C = 5 ; // return the color value so that their corresponding // index can be access. static int mapcolor ( char c ) { if ( c == 'r' ) { return 0 ; } else if ( c == 'g' ) { return 1 ; } else if ( c == 'b' ) { return 2 ; } else { return - 1 ; } } // Returns the maximum area of triangle from all // the possible triangles static double findarea ( char [ ] mat int r int c int [ ] top int [ ] bottom int [] left int [] right ) { double ans = . 0 ; // 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 . MaxValue && bottom [ y i ] != int . MinValue && left [ z ] != int . MaxValue ) { ans = Math . Max ( ans ( 1.0 / 2.0 ) * ( 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 . MaxValue && bottom [ y i ] != int . MinValue && right [ z ] != int . MinValue ) { ans = Math . Max ( ans ( 1.0 / 2.0 ) * ( bottom [ y i ] - top [ x i ]) * ( right [ z ] - i ) + 4 ); } } } } return ans ; } // Precompute the vertices of top bottom left // and right and then computing the maximum area. static double maxarea ( char [ ] mat int r int c ) { int [] left = { int . MaxValue int . MaxValue int . MaxValue }; int [] right = { int . MinValue int . MinValue int . MinValue }; int [ ] top = new int [ 3 C ]; int [ ] bottom = new int [ 3 C ]; // 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 ++ ) { int color = mapcolor ( mat [ i j ]); if ( color != - 1 ) { left [ color ] = Math . Min ( left [ color ] j ); right [ color ] = Math . Max ( right [ color ] j ); } } } // finding 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 ++ ) { int color = mapcolor ( mat [ i j ]); if ( color != - 1 ) { top [ color j ] = Math . Min ( top [ color j ] i ); bottom [ color j ] = Math . Max ( bottom [ color j ] i ); } } } return findarea ( mat R C top bottom left right ); } // Driven Program public static void Main ( string [] args ) { char [ ] mat = new char [ ] { { 'r' 'r' 'r' 'r' 'r' } { 'r' 'r' 'r' 'r' 'g' } { 'r' 'r' 'r' 'r' 'r' } { 'b' 'b' 'b' 'b' 'b' } }; Console . WriteLine ( maxarea ( mat R C )); } }산출:
10퀴즈 만들기
시간 복잡도: 오(R*C)
보조 공간: O(R + C)
원천: https://stackoverflow.com/questions/40078660/maximum-area-of-triangle-having-all-vertices-of- Different-color
