Maximale Fläche eines Dreiecks mit unterschiedlichen Scheitelpunktfarben
Gegeben sei eine Matrix von N Reihen und M Die Spalten bestehen aus drei Werten {r g b}. Die Aufgabe besteht darin, die Fläche des größten Dreiecks zu ermitteln, dessen eine Seite parallel zur y-Achse, d. h. vertikal, verläuft und dessen Farbe an allen drei Eckpunkten unterschiedlich ist.
Beispiele:
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.
Wir wissen, dass die Fläche eines Dreiecks = 1/2 * Basis * Höhe ist, daher müssen wir die Basis und Höhe des Dreiecks maximieren. Da eine Seite parallel zur y-Achse ist, können wir diese Seite als Basis des Dreiecks betrachten.
C++
Um die Basis zu maximieren, können wir das erste und letzte Vorkommen von {r g b} für jede Spalte ermitteln. Wir haben also zwei Sätze mit jeweils drei Werten für jede Spalte. Für die Basis in jeder Spalte stammt ein Scheitelpunkt aus der ersten Menge und der zweite Scheitelpunkt aus der zweiten Menge, sodass sie unterschiedliche Werte haben.
Um die Höhe einer beliebigen Säule als Basis zu maximieren, muss der dritte Scheitelpunkt so gewählt werden, dass der Scheitelpunkt am weitesten von der Säule entfernt auf der linken oder rechten Seite der Säule liegt und einen anderen Wert als die anderen beiden Scheitelpunkte aufweist.
Ermitteln Sie nun für jede Spalte die maximale Fläche des Dreiecks.
Nachfolgend finden Sie die Umsetzung dieses Ansatzes:
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 )); } }Ausgabe:
10Quiz erstellen
Zeitkomplexität: O(R * C)
Hilfsraum: O(R + C)
Quelle: https://stackoverflow.com/questions/40078660/maximum-area-of-triangle-having-all-vertices-of-different-color
