Dado un rectángulo [(x1, y1), (x2, y2)] que denota las coordenadas de la esquina inferior izquierda y la esquina superior derecha cuyos lados son paralelos a los ejes de coordenadas y N puntos en su perímetro (al menos uno en cada lado) . La tarea es maximizar el área de un triángulo formado por estos puntos.
Ejemplos:
Entrada: rectángulo[][]= {{0, 0}, {6, 6}},
coordenadas[][] = {{0, 2}, {0, 3}, {0, 5}, {2, 0}, {3, 0}, {6, 0}, {6, 4}, {1, 6}, {6, 6}}
Salida: 18
Explicación: Consulte la imagen a continuación para obtener una explicación .
Enfoque: para encontrar el triángulo de área máxima por coordenadas en un rectángulo dado, encuentre las coordenadas en cada lado que están más distantes entre sí. Entonces, supongamos que hay cuatro lados a, b, c, d donde a y c son la longitud del rectángulo y b, d son la anchura . Ahora el área máxima será
MAX (longitud * (distancia entre las coordenadas más lejanas en cualquiera de las anchuras) / 2, anchura * (distancia entre las coordenadas más lejanas en cualquiera de las longitudes) / 2).
Siga los pasos a continuación para resolver el problema dado.
- Calcula el largo = abs(x2 – x1) y el ancho = abs(y2 – y1)
- Encuentra las coordenadas que están más alejadas entre sí en cada lado.
- Utilice la fórmula mencionada anteriormente para calcular el área.
- Devolver el área encontrada.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// To find the maximum area of triangle
void maxTriangleArea(int rectangle[2][2],
int coordinates[][2],
int numberOfCoordinates)
{
int l1min = INT_MAX, l2min = INT_MAX,
l1max = INT_MIN, l2max = INT_MIN,
b1min = INT_MAX, b1max = INT_MIN,
b2min = INT_MAX, b2max = INT_MIN;
int l1Ycoordinate = rectangle[0][1];
int l2Ycoordinate = rectangle[1][1];
int b1Xcoordinate = rectangle[0][0];
int b2Xcoordinate = rectangle[1][0];
// Always consider side parallel
// to x-axis as length and
// side parallel to y-axis as breadth
for (int i = 0; i < numberOfCoordinates;
i++) {
coordinates[i][1];
// coordinate on l1
if (coordinates[i][1] == l1Ycoordinate) {
l1min = min(l1min,
coordinates[i][0]);
l1max = max(l1max,
coordinates[i][0]);
}
// Coordinate on l2
if (coordinates[i][1] == l2Ycoordinate) {
l2min = min(l2min,
coordinates[i][0]);
l2max = max(l2max,
coordinates[i][0]);
}
// Coordinate on b1
if (coordinates[i][0] == b1Xcoordinate) {
b1min = min(b1min,
coordinates[i][1]);
b1max = max(b1max,
coordinates[i][1]);
}
// Coordinate on b2
if (coordinates[i][0] == b2Xcoordinate) {
b2min = min(b2min,
coordinates[i][1]);
b2max = max(b2max,
coordinates[i][1]);
}
}
// Find maximum possible distance
// on length
int maxOfLength = max(abs(l1max - l1min),
abs(l2max - l2min));
// Find maximum possible distance
// on breadth
int maxofBreadth = max(abs(b1max - b1min),
abs(b2max - b2min));
// Calculate result base * height / 2
float result
= max((maxofBreadth
* (abs(rectangle[0][0]
- rectangle[1][0]))),
(maxOfLength
* (abs(rectangle[0][1]
- rectangle[1][1]))))
/ 2.0;
// Print the result
cout << result;
}
// Driver Code
int main()
{
// Rectangle with x1, y1 and x2, y2
int rectangle[2][2] = { { 0, 0 },
{ 6, 6 } };
// Coordinates on sides of given rectangle
int coordinates[9][2]
= { { 0, 2 }, { 0, 3 }, { 0, 5 },
{ 2, 0 }, { 3, 0 }, { 6, 0 },
{ 6, 4 }, { 1, 6 }, { 6, 6 } };
int numberOfCoordinates
= sizeof(coordinates) / sizeof(coordinates[0]);
maxTriangleArea(rectangle, coordinates,
numberOfCoordinates);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// To find the maximum area of triangle
static void maxTriangleArea(int[ ][ ] rectangle,
int[ ][ ] coordinates,
int numberOfCoordinates)
{
int l1min = Integer.MAX_VALUE, l2min = Integer.MAX_VALUE,
l1max = Integer.MIN_VALUE, l2max = Integer.MIN_VALUE,
b1min = Integer.MAX_VALUE, b1max = Integer.MIN_VALUE,
b2min = Integer.MAX_VALUE, b2max = Integer.MIN_VALUE;
int l1Ycoordinate = rectangle[0][1];
int l2Ycoordinate = rectangle[1][1];
int b1Xcoordinate = rectangle[0][0];
int b2Xcoordinate = rectangle[1][0];
// Always consider side parallel
// to x-axis as length and
// side parallel to y-axis as breadth
for (int i = 0; i < numberOfCoordinates; i++) {
// coordinate on l1
if (coordinates[i][1] == l1Ycoordinate) {
l1min = Math.min(l1min,
coordinates[i][0]);
l1max = Math.max(l1max,
coordinates[i][0]);
}
// Coordinate on l2
if (coordinates[i][1] == l2Ycoordinate) {
l2min = Math.min(l2min,
coordinates[i][0]);
l2max = Math.max(l2max,
coordinates[i][0]);
}
// Coordinate on b1
if (coordinates[i][0] == b1Xcoordinate) {
b1min = Math.min(b1min,
coordinates[i][1]);
b1max = Math.max(b1max,
coordinates[i][1]);
}
// Coordinate on b2
if (coordinates[i][0] == b2Xcoordinate) {
b2min = Math.min(b2min,
coordinates[i][1]);
b2max = Math.max(b2max,
coordinates[i][1]);
}
}
// Find maximum possible distance
// on length
int maxOfLength = Math.max(Math.abs(l1max - l1min),
Math.abs(l2max - l2min));
// Find maximum possible distance
// on breadth
int maxofBreadth = Math.max(Math.abs(b1max - b1min),
Math.abs(b2max - b2min));
// Calculate result base * height / 2
int result
= Math.max((maxofBreadth
* (Math.abs(rectangle[0][0]
- rectangle[1][0]))),
(maxOfLength
* (Math.abs(rectangle[0][1]
- rectangle[1][1]))))
/ 2;
// Print the result
System.out.print(result);
}
// Driver Code
public static void main (String[] args)
{
// Rectangle with x1, y1 and x2, y2
int[ ][ ] rectangle = { { 0, 0 },
{ 6, 6 } };
// Coordinates on sides of given rectangle
int[ ][ ] coordinates
= { { 0, 2 }, { 0, 3 }, { 0, 5 },
{ 2, 0 }, { 3, 0 }, { 6, 0 },
{ 6, 4 }, { 1, 6 }, { 6, 6 } };
int numberOfCoordinates
= coordinates.length;
maxTriangleArea(rectangle, coordinates,
numberOfCoordinates);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach # To find the maximum area of triangle def maxTriangleArea(rectangle, coordinates, numberOfCoordinates): l1min = 10 ** 9 l2min = 10 ** 9 l1max = 10 ** -9 l2max = 10 ** -9 b1min = 10 ** 9 b1max = 10 ** -9 b2min = 10 ** 9 b2max = 10 ** -9 l1Ycoordinate = rectangle[0][1]; l2Ycoordinate = rectangle[1][1]; b1Xcoordinate = rectangle[0][0]; b2Xcoordinate = rectangle[1][0]; # Always consider side parallel # to x-axis as length and # side parallel to y-axis as breadth for i in range(numberOfCoordinates): coordinates[i][1]; # coordinate on l1 if (coordinates[i][1] == l1Ycoordinate) : l1min = min(l1min, coordinates[i][0]); l1max = max(l1max, coordinates[i][0]); # Coordinate on l2 if (coordinates[i][1] == l2Ycoordinate): l2min = min(l2min, coordinates[i][0]); l2max = max(l2max, coordinates[i][0]); # Coordinate on b1 if (coordinates[i][0] == b1Xcoordinate): b1min = min(b1min, coordinates[i][1]); b1max = max(b1max, coordinates[i][1]); # Coordinate on b2 if (coordinates[i][0] == b2Xcoordinate): b2min = min(b2min, coordinates[i][1]); b2max = max(b2max, coordinates[i][1]); # Find maximum possible distance # on length maxOfLength = max(abs(l1max - l1min), abs(l2max - l2min)); # Find maximum possible distance # on breadth maxofBreadth = max(abs(b1max - b1min), abs(b2max - b2min)); # Calculate result base * height / 2 result = max((maxofBreadth * (abs(rectangle[0][0] - rectangle[1][0]))), (maxOfLength * (abs(rectangle[0][1] - rectangle[1][1])))) / 2.0; # Print the result print(int(result)); # Driver Code # Rectangle with x1, y1 and x2, y2 rectangle = [[0, 0],[6, 6]]; # Coordinates on sides of given rectangle coordinates = [[0, 2], [0, 3], [0, 5], [2, 0], [3, 0], [6, 0], [6, 4], [1, 6], [6, 6]]; numberOfCoordinates = len(coordinates) maxTriangleArea(rectangle, coordinates, numberOfCoordinates); # This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG {
// To find the maximum area of triangle
static void maxTriangleArea(int[,] rectangle,
int[,] coordinates,
int numberOfCoordinates)
{
int l1min = Int32.MaxValue, l2min = Int32.MaxValue,
l1max = Int32.MinValue, l2max = Int32.MinValue,
b1min = Int32.MaxValue, b1max = Int32.MinValue,
b2min = Int32.MaxValue, b2max = Int32.MinValue;
int l1Ycoordinate = rectangle[0,1];
int l2Ycoordinate = rectangle[1,1];
int b1Xcoordinate = rectangle[0,0];
int b2Xcoordinate = rectangle[1,0];
// Always consider side parallel
// to x-axis as length and
// side parallel to y-axis as breadth
for (int i = 0; i < numberOfCoordinates; i++) {
// coordinate on l1
if (coordinates[i,1] == l1Ycoordinate) {
l1min = Math.Min(l1min,
coordinates[i,0]);
l1max = Math.Max(l1max,
coordinates[i,0]);
}
// Coordinate on l2
if (coordinates[i,1] == l2Ycoordinate) {
l2min = Math.Min(l2min,
coordinates[i,0]);
l2max = Math.Max(l2max,
coordinates[i,0]);
}
// Coordinate on b1
if (coordinates[i,0] == b1Xcoordinate) {
b1min = Math.Min(b1min,
coordinates[i,1]);
b1max = Math.Max(b1max,
coordinates[i,1]);
}
// Coordinate on b2
if (coordinates[i,0] == b2Xcoordinate) {
b2min = Math.Min(b2min,
coordinates[i,1]);
b2max = Math.Max(b2max,
coordinates[i,1]);
}
}
// Find maximum possible distance
// on length
int maxOfLength = Math.Max(Math.Abs(l1max - l1min),
Math.Abs(l2max - l2min));
// Find maximum possible distance
// on breadth
int maxofBreadth = Math.Max(Math.Abs(b1max - b1min),
Math.Abs(b2max - b2min));
// Calculate result base * height / 2
int result
= Math.Max((maxofBreadth
* (Math.Abs(rectangle[0,0]
- rectangle[1,0]))),
(maxOfLength
* (Math.Abs(rectangle[0,1]
- rectangle[1,1]))))
/ 2;
// Print the result
Console.Write(result);
}
// Driver Code
public static void Main ()
{
// Rectangle with x1, y1 and x2, y2
int[,] rectangle = { { 0, 0 },
{ 6, 6 } };
// Coordinates on sides of given rectangle
int[,] coordinates
= { { 0, 2 }, { 0, 3 }, { 0, 5 },
{ 2, 0 }, { 3, 0 }, { 6, 0 },
{ 6, 4 }, { 1, 6 }, { 6, 6 } };
int numberOfCoordinates
= coordinates.GetLength(0);
maxTriangleArea(rectangle, coordinates,
numberOfCoordinates);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// To find the maximum area of triangle
function maxTriangleArea(rectangle,
coordinates,
numberOfCoordinates) {
let l1min = Number.MAX_VALUE, l2min = Number.MAX_VALUE,
l1max = Number.MIN_VALUE, l2max = Number.MIN_VALUE,
b1min = Number.MAX_VALUE, b1max = Number.MIN_VALUE,
b2min = Number.MAX_VALUE, b2max = Number.MIN_VALUE;
let l1Ycoordinate = rectangle[0][1];
let l2Ycoordinate = rectangle[1][1];
let b1Xcoordinate = rectangle[0][0];
let b2Xcoordinate = rectangle[1][0];
// Always consider side parallel
// to x-axis as length and
// side parallel to y-axis as breadth
for (let i = 0; i < numberOfCoordinates;
i++) {
coordinates[i][1];
// coordinate on l1
if (coordinates[i][1] == l1Ycoordinate) {
l1min = Math.min(l1min,
coordinates[i][0]);
l1max = Math.max(l1max,
coordinates[i][0]);
}
// Coordinate on l2
if (coordinates[i][1] == l2Ycoordinate) {
l2min = Math.min(l2min,
coordinates[i][0]);
l2max = Math.max(l2max,
coordinates[i][0]);
}
// Coordinate on b1
if (coordinates[i][0] == b1Xcoordinate) {
b1min = Math.min(b1min,
coordinates[i][1]);
b1max = Math.max(b1max,
coordinates[i][1]);
}
// Coordinate on b2
if (coordinates[i][0] == b2Xcoordinate) {
b2min = Math.min(b2min,
coordinates[i][1]);
b2max = Math.max(b2max,
coordinates[i][1]);
}
}
// Find maximum possible distance
// on length
let maxOfLength = Math.max(Math.abs(l1max - l1min),
Math.abs(l2max - l2min));
// Find maximum possible distance
// on breadth
let maxofBreadth = Math.max(Math.abs(b1max - b1min),
Math.abs(b2max - b2min));
// Calculate result base * height / 2
let result
= Math.max((maxofBreadth
* (Math.abs(rectangle[0][0]
- rectangle[1][0]))),
(maxOfLength
* (Math.abs(rectangle[0][1]
- rectangle[1][1]))))
/ 2.0;
// Print the result
document.write(result);
}
// Driver Code
// Rectangle with x1, y1 and x2, y2
let rectangle = [[0, 0],
[6, 6]];
// Coordinates on sides of given rectangle
let coordinates
= [[0, 2], [0, 3], [0, 5],
[2, 0], [3, 0], [6, 0],
[6, 4], [1, 6], [6, 6]];
let numberOfCoordinates
= coordinates.length;
maxTriangleArea(rectangle, coordinates,
numberOfCoordinates);
// This code is contributed by Potta Lokesh
</script>
Producción
18
Complejidad temporal: O(N), donde N es el número de coordenadas dadas.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA