Longitud mínima del camino más corto de un triángulo

Dados N puntos en el plano, ( X ₁ , Y ₁ ), ( X ₂ , Y ₂ ), ( X ₃ , Y ₃ ), ……, ( X _N , Y _N ). La tarea es calcular la longitud mínima del lado más corto del triángulo. y la ruta o los puntos para colocar un triángulo isósceles con cualquiera de los dos lados del triángulo en el eje de coordenadas (eje X y eje Y) para cubrir todos los puntos.
Nota: Un punto está cubierto si se encuentra dentro del triángulo o en el lado del triángulo.
Ejemplos:
 

Entrada: (1, 3), (1, 1), (2, 1), (2, 2) 
Salida: Longitud -> 4 , Ruta -> ( 1, 4 ) y ( 4, 1 )
Entrada: (1 , 2), (1, 1), (2, 1) 
Salida: Longitud -> 3 , Ruta -> ( 1, 3 ) y ( 3, 1 )

En el primer ejemplo, la longitud mínima del camino más corto es igual a la suma máxima de los puntos, que es 1+3 o 2+2. Entonces, el camino que cubrirá todos los puntos es (1, 4) y (4, 1) en el eje de coordenadas.
A continuación se muestra el algoritmo paso a paso para resolver este problema: 
 

1. Inicializar ‘N’ puntos en un plano.
2. Recorre cada punto y encuentra la suma de cada punto y guárdala en una variable ‘respuesta’.
3. Reemplace la siguiente suma máxima de los puntos con la suma anterior.
4. Luego obtendrá la ruta en un eje de coordenadas (1, respuesta) y (respuesta, 1) que cubrirá todos los puntos del triángulo isósceles.

A continuación se muestra la implementación del algoritmo anterior: 
 

// C++ program to illustrate
// the above problem
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
// function to get the minimum length of
// the shorter side of the triangle
void shortestLength(int n, int x[], int y[])
{
        int answer = 0;
 
    // traversing through each points on the plane
    int i = 0;
    while (n--) {
        // if sum of a points is greater than the
        // previous one, the maximum gets replaced
        if (x[i] + y[i] > answer)
            answer = x[i] + y[i];
 
        i++;
    }
 
    // print the length
    cout << "Length -> " << answer << endl;
    cout << "Path -> "
         << "( 1, " << answer << " )"
         << "and ( " << answer << ", 1 )";
}
 
// Driver code
int main()
{
    // initialize the number of points
    int n = 4;
 
    // points on the plane
    int x[n] = { 1, 4, 2, 1 };
    int y[n] = { 4, 1, 1, 2 };
 
    shortestLength(n, x, y);
 
    return 0;
}

// Java program to illustrate
// the above problem
class GFG
{
 
// function to get the minimum length of
// the shorter side of the triangle
static void shortestLength(int n, int x[],
                           int y[])
{
    int answer = 0;
 
    // traversing through each
    // points on the plane
    int i = 0;
    while (n != 0 && i < x.length)
    {
        // if sum of a points is greater
        // than the previous one, the
        // maximum gets replaced
        if (x[i] + y[i] > answer)
            answer = x[i] + y[i];
 
        i++;
    }
 
    // print the length
    System.out.println("Length -> " + answer );
    System.out.println("Path -> " +
                       "( 1, " + answer + " )" +
                       "and ( " + answer + ", 1 )");
}
 
// Driver code
public static void main(String[] args)
{
    // initialize the number of points
    int n = 4;
 
    // points on the plane
    int x[] = new int[] { 1, 4, 2, 1 };
    int y[] = new int[] { 4, 1, 1, 2 };
 
    shortestLength(n, x, y);
}
}
 
// This code is contributed
// by Prerna Saini

# Python 3 program to illustrate
# the above problem
 
# function to get the minimum length of
# the shorter side of the triangle
def shortestLength(n, x, y):
    answer = 0
 
    # traversing through each
    # points on the plane
    i = 0
    while n > 0:
         
        # if sum of a points is greater
        # than the previous one, the
        # maximum gets replaced
        if (x[i] + y[i] > answer):
            answer = x[i] + y[i]
 
        i += 1
        n -= 1
 
    # print the length
    print("Length -> "+ str(answer))
    print( "Path -> "+
        "( 1, " +str(answer)+ " )"+
        "and ( "+str( answer) +", 1 )")
 
# Driver code
if __name__ == "__main__":
     
    # initialize the number of points
    n = 4
 
    # points on the plane
    x = [ 1, 4, 2, 1 ]
    y = [ 4, 1, 1, 2 ]
    shortestLength(n, x, y)
 
# This code is contributed
# by ChitraNayal

// C# program to illustrate
// the above problem
using System;
 
class GFG
{
 
// function to get the minimum
// length of the shorter side
// of the triangle
static void shortestLength(int n, int[] x,
                           int[] y)
{
    int answer = 0;
 
    // traversing through each
    // points on the plane
    int i = 0;
    while (n != 0 && i < x.Length)
    {
        // if sum of a points is greater
        // than the previous one, the
        // maximum gets replaced
        if (x[i] + y[i] > answer)
            answer = x[i] + y[i];
 
        i++;
    }
 
    // print the length
    Console.WriteLine("Length -> " + answer);
    Console.WriteLine("Path -> " +
                      "( 1, " + answer + " )" +
                      "and ( " + answer + ", 1 )");
}
 
// Driver code
static public void Main ()
{
     
    // initialize the
    // number of points
    int n = 4;
 
    // points on the plane
    int[] x = new int[] { 1, 4, 2, 1 };
    int[] y = new int[] { 4, 1, 1, 2 };
 
    shortestLength(n, x, y);
}
}
 
// This code is contributed by Mahadev

<?php
// PHP program to illustrate
// the above problem
 
// function to get the minimum length of
// the shorter side of the triangle
function shortestLength($n, &$x, &$y)
{
    $answer = 0;
 
    // traversing through each
    // points on the plane
    $i = 0;
    while ($n--)
    {
         
        // if sum of a points is greater
        // than the previous one, the
        // maximum gets replaced
        if ($x[$i] + $y[$i] > $answer)
            $answer = $x[$i] + $y[$i];
 
        $i++;
    }
 
    // print the length
    echo "Length -> ".$answer."\n";
    echo "Path -> ". "( 1, " .$answer ." )".
         "and ( " .$answer . ", 1 )";
}
 
// Driver code
 
// initialize the number of points
$n = 4;
 
// points on the plane
$x = array(1, 4, 2, 1 );
$y = array(4, 1, 1, 2 );
 
shortestLength($n, $x, $y);
 
// This code is contributed
// by ChitraNayal
?>

<script>
 
// Javascript program to illustrate
// the above problem
 
// function to get the minimum length of
// the shorter side of the triangle
function shortestLength(n, x, y)
{
    let answer = 0;
 
    // traversing through each
    // points on the plane
    let i = 0;
    while (n != 0 && i < x.length)
    {
        // if sum of a points is greater
        // than the previous one, the
        // maximum gets replaced
        if (x[i] + y[i] > answer)
            answer = x[i] + y[i];
 
        i++;
    }
 
    // print the length
    document.write("Length -> " + answer + "<br/>");
    document.write("Path -> " +
                       "( 1, " + answer + " )" +
                       "and ( " + answer + ", 1 )");
}
 
 
// Driver Code
 
    // initialize the number of points
    let n = 4;
 
    // points on the plane
    let x = [ 1, 4, 2, 1 ];
    let y = [ 4, 1, 1, 2 ];
 
    shortestLength(n, x, y);
 
</script>

Length -> 5
Path -> ( 1, 5 )and ( 5, 1 )

Complejidad temporal : O(n) donde n es el número de puntos.
Espacio Auxiliar : O(1)