Encuentre la distancia máxima posible desde el origen usando puntos dados

Dados N puntos bidimensionales. La tarea es encontrar la distancia máxima posible desde el origen usando puntos dados. Usando el i ^-ésimo punto (x _i , y _i ) uno puede moverse de (a, b) a (a + x _i , b + y _i ) . 
Nota: N se encuentra entre 1 y 1000 y cada punto se puede usar como máximo una vez.
Ejemplos: 
 

Entrada: arr[][] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}} 
Salida: 14.14 
El punto más lejano al que podemos movernos es (10, 10).
Entrada: arr[][] = {{0, 10}, {5, -5}, {-5, -5}} 
Salida: 10,00 
 

Enfoque: La observación clave es que cuando los puntos se ordenan por los ángulos que forman sus vectores con el eje x, la respuesta incluirá vectores en algún rango contiguo. Una prueba de este hecho se puede leer desde aquí . Entonces, la solución es bastante fácil de implementar. Iterar sobre todos los rangos posibles y calcular las respuestas para cada uno de ellos, tomando el máximo como resultado. Cuando se implementa adecuadamente, se trata de un enfoque O(N ² ).
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum possible
// distance from origin using given points.
void Max_Distance(vector<pair<int, int> >& xy, int n)
{
    // Sort the points with their tan angle
    sort(xy.begin(), xy.end(), [](const pair<int, int>&l,
                                  const pair<int, int>& r) {
        return atan2l(l.second, l.first)
               < atan2l(r.second, r.first);
    });
 
    // Push the whole vector
    for (int i = 0; i < n; i++)
        xy.push_back(xy[i]);
 
    // To store the required answer
    int res = 0;
 
    // Find the maximum possible answer
    for (int i = 0; i< n; i++) {
        int x = 0, y = 0;
        for (int j = i; j <i + n; j++) {
            x += xy[j].first;
            y += xy[j].second;
            res = max(res, x * x + y * y);
        }
    }
 
    // Print the required answer
    cout << fixed << setprecision(2) << sqrtl(res);
}
 
// Driver code
int main()
{
    vector<pair<int, int>> vec = { { 1, 1 },
                                    { 2, 2 },
                                    { 3, 3 },
                                    { 4, 4 } };
 
    int n = vec.size();
 
    // Function call
    Max_Distance(vec, n);
 
    return 0;
}

// JavaScript implementation of the approach
 
// Function to implement the custom sort
function myCustomSort(l, r){
    return Math.atan2(l[1], l[0]) < Math.atan2(r[1], r[0]);
}
 
// Function to find the maximum possible
// distance from origin using given points.
function Max_Distance(xy, n)
{
    // Sort the points with their tan angle
    xy.sort(myCustomSort);
 
    // Push the whole vector
    for (let i = 0; i < n; i++)
        xy.push(xy[i]);
 
    // To store the required answer
    let res = 0;
 
    // Find the maximum possible answer
    for (let i = 0; i< n; i++) {
        let x = 0, y = 0;
        for (let j = i; j <i + n; j++) {
            x += xy[j][0];
            y += xy[j][1];
            res = Math.max(res, x * x + y * y);
        }
    }
 
    // Print the required answer
    console.log(Math.sqrt(res).toFixed(2));
 
}
 
// Driver code
let vec = [[1, 1],
           [2, 2],
           [3, 3],
           [4, 4]];
 
let n = vec.length;
 
// Function call
Max_Distance(vec, n);
 
// The code is contributed by Gautam goel (gautmgoel962)

14.14

Complejidad del tiempo: O(n^2)

Espacio Auxiliar: O(1)