Dada una array de N filas y M columnas, consta de tres valores {r, g, b}. La tarea es encontrar el área del triángulo más grande que tiene un lado paralelo al eje y, es decir, vertical y el color de los tres vértices es diferente.
Ejemplos:
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 (0,0) containing r, (1,4) containing g, (3,0) containing b.
Sabemos que el área de un triángulo = 1/2 * base * altura, por lo que debemos maximizar la base y la altura del triángulo. Como un lado es paralelo al eje y, podemos considerar ese lado como la base del triángulo.
Para maximizar la base, podemos encontrar la primera y la última ocurrencia de {r, g, b} para cada columna. Así que tenemos dos conjuntos de 3 valores para cada columna. Para la base en cualquier columna, un vértice es del primer conjunto y el segundo vértice del segundo conjunto, de modo que tienen valores diferentes.
Para maximizar la altura, para cualquier columna como base, el tercer vértice debe elegirse de tal manera que el vértice esté más alejado de la columna, en el lado izquierdo o derecho de la columna y tenga un valor diferente de los otros dos vértices.
Ahora, para cada columna, encuentre el área máxima del triángulo.
A continuación se muestra la implementación de este enfoque:
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);
}
}
// 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;
}
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)
# 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 Jain
Producción:
10
Complejidad de tiempo: O(R * C)
Espacio auxiliar: O(R + C)
Fuente: http://stackoverflow.com/questions/40078660/maximum-area-of-triangle-have-all-vertices-of- different- color
Este artículo es una contribución de Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA