Distancia máxima entre dos puntos en el plano de coordenadas utilizando el método del calibrador giratorio

Prerrequisitos: Casco convexo de Graham Scan , Orientación .
Dado un conjunto de N puntos en un plano de coordenadas, la tarea es encontrar la distancia máxima entre dos puntos cualesquiera en el conjunto de planos dado.

Ejemplos: 

Entrada: n = 4, Puntos: (0, 3), (3, 0), (0, 0), (1, 1) Salida: Distancia máxima = 4,24264 
Explicación : 
Los 
puntos que tienen una distancia máxima entre ellos son (0, 3 ) y (3, 0) 

Entrada: n = 5, Puntos: (4, 0), (0, 2), (-1, -7), (1, 10), (2, -3) Salida: Distancia máxima = 17,11724 Explicación 
: Puntos 
que 
tienen distancia máxima entre ellos son (-1, 7) y (1, 10) 

Enfoque ingenuo: la idea ingenua es probar todos los pares posibles de puntos del conjunto dado y calcular las distancias entre cada uno de ellos e imprimir la distancia máxima entre todos los pares.

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

#include <bits/stdc++.h>
using namespace std;
 
// Function calculates distance
// between two points
long dist(pair<long, long> p1,
          pair<long, long> p2)
{
    long x0 = p1.first - p2.first;
    long y0 = p1.second - p2.second;
    return x0 * x0 + y0 * y0;
}
 
// Function to find the maximum
// distance between any two points
double maxDist(pair<long, long> p[], int n)
{
    double Max = 0;
 
    // Iterate over all possible pairs
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
             
            // Update max
            Max = max(Max, (double)dist(p[i],
                                        p[j]));
        }
    }
 
    // Return actual distance
    return sqrt(Max);
}
 
// Driver code  
int main()
{
     
    // Number of points
    int n = 5;
 
    pair<long, long> p[n];
 
    // Given points
    p[0].first = 4, p[0].second = 0;
    p[1].first = 0, p[1].second = 2;
    p[2].first = -1, p[2].second = -7;
    p[3].first = 1, p[3].second = 10;
    p[4].first = 2, p[4].second = -3;
 
    // Function call
    cout << fixed << setprecision(14)
         << maxDist(p, n) <<endl;
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

import java.awt.*;
import java.util.ArrayList;
 
public class Main {
 
    // Function calculates distance
    // between two points
    static long dist(Point p1, Point p2)
    {
        long x0 = p1.x - p2.x;
        long y0 = p1.y - p2.y;
        return x0 * x0 + y0 * y0;
    }
 
    // Function to find the maximum
    // distance between any two points
    static double maxDist(Point p[])
    {
        int n = p.length;
        double max = 0;
 
        // Iterate over all possible pairs
        for (int i = 0; i < n; i++) {
 
            for (int j = i + 1; j < n; j++) {
 
                // Update max
                max = Math.max(max,
                               dist(p[i],
                                    p[j]));
            }
        }
 
        // Return actual distance
        return Math.sqrt(max);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Number of points
        int n = 5;
 
        Point p[] = new Point[n];
 
        // Given points
        p[0] = new Point(4, 0);
        p[1] = new Point(0, 2);
        p[2] = new Point(-1, -7);
        p[3] = new Point(1, 10);
        p[4] = new Point(2, -3);
 
        // Function Call
        System.out.println(maxDist(p));
    }
}

from math import sqrt
 
# Function calculates distance
# between two points
def dist(p1, p2):
     
    x0 = p1[0] - p2[0]
    y0 = p1[1] - p2[1]
    return x0 * x0 + y0 * y0
 
# Function to find the maximum
# distance between any two points
def maxDist(p):
 
    n = len(p)
    maxm = 0
 
    # Iterate over all possible pairs
    for i in range(n):
        for j in range(i + 1, n):
             
            # Update maxm
            maxm = max(maxm, dist(p[i], p[j]))
 
    # Return actual distance
    return sqrt(maxm)
     
# Driver Code
if __name__ == '__main__':
     
    # Number of points
    n = 5
 
    p = []
     
    # Given points
    p.append([4, 0])
    p.append([0, 2])
    p.append([-1, -7])
    p.append([1, 10])
    p.append([2, -3])
 
    # Function Call
    print(maxDist(p))
 
# This code is contributed by mohit kumar 29

using System;
class GFG {
     
    // Function calculates distance
    // between two points
    static long dist(Tuple<int, int> p1, Tuple<int, int> p2)
    {
        long x0 = p1.Item1 - p2.Item1;
        long y0 = p1.Item2 - p2.Item2;
        return x0 * x0 + y0 * y0;
    }
  
    // Function to find the maximum
    // distance between any two points
    static double maxDist(Tuple<int, int>[] p)
    {
        int n = p.Length;
        double max = 0;
  
        // Iterate over all possible pairs
        for (int i = 0; i < n; i++) {
  
            for (int j = i + 1; j < n; j++) {
  
                // Update max
                max = Math.Max(max, dist(p[i],p[j]));
            }
        }
  
        // Return actual distance
        return Math.Sqrt(max);
    }
 
  // Driver code
  static void Main() {
      
        // Given points
        Tuple<int, int>[] p =
        {
            Tuple.Create(4, 0),
            Tuple.Create(0, 2),
            Tuple.Create(-1, -7),
            Tuple.Create(1, 10),
            Tuple.Create(2, -3),
        };
       
        // Function Call
        Console.WriteLine(maxDist(p));
  }
}
 
// This code is contributed by divyesh072019

<script>
      // Function calculates distance
      // between two points
      function dist(p1, p2) {
        var x0 = p1[0] - p2[0];
        var y0 = p1[1] - p2[1];
        return x0 * x0 + y0 * y0;
      }
      // Function to find the maximum
      // distance between any two points
      function maxDist(p) {
        var n = p.length;
        var maxm = 0;
 
        // Iterate over all possible pairs
        for (let i = 0; i < n; i++) {
          for (let j = i + 1; j < n; j++) {
            // Update maxm
            maxm = Math.max(maxm, dist(p[i], p[j]));
          }
        }
        // Return actual distance
        return Math.sqrt(maxm);
      }
      // Driver Code
      // Number of points
      var n = 5;
 
      var p = [];
 
      // Given points
      p.push([4, 0]);
      p.push([0, 2]);
      p.push([-1, -7]);
      p.push([1, 10]);
      p.push([2, -3]);
 
      // Function Call
      document.write(maxDist(p));
    </script>

17.11724276862369

Complejidad Temporal: O(N ² ), donde N es el número total de puntos. 
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque ingenuo anterior se puede optimizar utilizando el método del calibrador giratorio .

Rotating Calipers es un método para resolver una serie de problemas del campo de la geometría computacional. Se asemeja a la idea de girar un calibrador ajustable alrededor del exterior del casco convexo de un polígono. Originalmente, este método se inventó para calcular el diámetro de polígonos convexos. También se puede usar para calcular la distancia mínima y máxima entre dos polígonos convexos, la intersección de polígonos convexos, la distancia máxima entre dos puntos en un polígono y muchas cosas más. 

Para implementar el método anterior, utilizaremos el concepto de casco convexo . Antes de comenzar una discusión adicional sobre el enfoque óptimo, necesitamos saber lo siguiente:

• Área sin signo del triángulo: si nos dan tres puntos P1 (x1, y1), P2 (x2, y2) y P3 (x3, y3) entonces

• es el área firmada del triángulo. Si el área es positiva, entonces tres puntos están en el sentido de las agujas del reloj, de lo contrario, están en el sentido contrario a las agujas del reloj y si el área es igual a cero, los puntos son colineales. Si tomamos el valor absoluto , esto representará el área sin signo del triángulo. Aquí, sin signo básicamente significa área sin dirección, es decir, solo necesitamos el valor relativo absoluto del área. Por lo tanto, podemos eliminar (1/2) de la fórmula. Por eso,

Área relativa del triángulo = abs((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1)) 

• Puntos antípodas: Son aquellos puntos que son diametralmente opuestos entre sí. Pero para nosotros, los puntos antípodas son aquellos que están más alejados entre sí en el polígono convexo. Si elegimos un punto del conjunto dado, entonces este punto solo puede alcanzar su distancia máxima si y solo si podemos encontrar su punto antípoda del conjunto dado.

A continuación se muestran los pasos:

1. Dos puntos que tengan la distancia máxima deben estar en el límite del polígono convexo formado a partir del conjunto dado. Por lo tanto, utilice el método de casco convexo de Graham Scan para organizar los puntos en el sentido contrario a las agujas del reloj.
2. Tenemos N puntos, inicialmente comenzamos desde el punto P1 e incluimos esos puntos del conjunto de puntos dados, de modo que el área de la región siempre aumenta al incluir cualquier punto del conjunto.
3. A partir del punto P1 , elija K = 2 e incremente K mientras el área (PN, P1, PK) aumenta y deténgase antes de que comience a disminuir. Ahora el punto PK actual podría ser el punto antípoda para P1 . De manera similar, encuentre el punto antípoda para p2 encontrando el área (P1, P2, PK) e incrementando la forma K donde nos detuvimos previamente y así sucesivamente.
4. Continúe actualizando la distancia máxima para cada punto antípoda que ocurre en los pasos anteriores, ya que la distancia entre el punto inicial y el punto al incluir el área era máxima.

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

// Java Program for the above approach
import java.awt.*;
import java.util.*;
import java.util.Map.Entry;
 
public class Main {
 
    // Function to detect the orientation
    static int orientation(Point p,
                           Point q,
                           Point r)
    {
        int x = area(p, q, r);
 
        // If area > 0 then
        // points are clockwise
        if (x > 0) {
            return 1;
        }
 
        // If area<0 then
        // points are counterclockwise
        if (x < 0) {
            return -1;
        }
 
        // If area is 0 then p, q
        // and r are co-linear
        return 0;
    }
 
    // Function to find the area
    static int area(Point p, Point q, Point r)
    {
        // 2*(area of triangle)
        return ((p.y - q.y) * (q.x - r.x)
                - (q.y - r.y) * (p.x - q.x));
    }
 
    // Function to find the absolute Area
    static int absArea(Point p,
                       Point q, Point r)
    {
        // Unsigned area
        // 2*(area of triangle)
        return Math.abs(area(p, q, r));
    }
 
    // Function to find the distance
    static int dist(Point p1, Point p2)
    {
        // squared-distance b/w
        // p1 and p2 for precision
        return ((p1.x - p2.x) * (p1.x - p2.x)
                + (p1.y - p2.y) * (p1.y - p2.y));
    }
 
    // Function to implement Convex Hull
    // Approach
    static ArrayList<Point>
    convexHull(Point points[])
    {
        int n = points.length;
 
        Point min = new Point(Integer.MAX_VALUE,
                              Integer.MAX_VALUE);
 
        // Choose point having min.
        // y-coordinate and if two points
        // have same y-coordinate choose
        // the one with minimum x-coordinate
        int ind = -1;
 
        // Iterate Points[]
        for (int i = 0; i < n; i++) {
            if (min.y > points[i].y) {
                min.y = points[i].y;
                min.x = points[i].x;
                ind = i;
            }
            else if (min.y == points[i].y
                     && min.x > points[i].x) {
                min.x = points[i].x;
                ind = i;
            }
        }
        points[ind] = points[0];
        points[0] = min;
 
        // Sort points which have
        // minimum polar angle wrt
        // Point min
        Arrays.sort(points, 1, n,
                    new Comparator<Point>() {
 
                        @Override
                        public int compare(Point o1,
                                           Point o2)
                        {
 
                            int o = orientation(min, o1, o2);
 
                            // If points are co-linear
                            // choose the one having smaller
                            // distance with min first.
                            if (o == 0) {
                                return dist(o1, min)
                                    - dist(o2, min);
                            }
 
                            // If clockwise then swap
                            if (o == 1) {
                                return 1;
                            }
 
                            // If anticlockwise then
                            // don't swap
                            return -1;
                        }
                    });
 
        Stack<Point> st = new Stack<>();
 
        // First hull point
        st.push(points[0]);
 
        int k;
        for (k = 1; k < n - 1; k++) {
            if (orientation(points[0],
                            points[k],
                            points[k + 1])
                != 0)
                break;
        }
 
        // Second hull point
        st.push(points[k]);
 
        for (int i = k + 1; i < n; i++) {
            Point top = st.pop();
 
            while (orientation(st.peek(),
                               top,
                               points[i])
                   >= 0) {
                top = st.pop();
            }
 
            st.push(top);
            st.push(points[i]);
        }
 
        ArrayList<Point> hull
            = new ArrayList<>();
 
        // Iterate stack and add node to hull
        for (int i = 0; i < st.size(); i++) {
            hull.add(st.get(i));
        }
        return hull;
    }
 
    // Function to find the maximum
    // distance between any two points
    // from a set of given points
    static double
    rotatingCaliper(Point points[])
    {
        // Takes O(n)
        ArrayList<Point> convexHull
            = convexHull(points);
        int n = convexHull.size();
 
        // Convex hull point in counter-
        // clockwise order
        Point hull[] = new Point[n];
        n = 0;
 
        while (n < convexHull.size()) {
            hull[n] = convexHull.get(n++);
        }
 
        // Base Cases
        if (n == 1)
            return 0;
        if (n == 2)
            return Math.sqrt(dist(hull[0], hull[1]));
        int k = 1;
 
        // Find the farthest vertex
        // from hull[0] and hull[n-1]
        while (absArea(hull[n - 1],
                       hull[0],
                       hull[(k + 1) % n])
               > absArea(hull[n - 1],
                         hull[0],
                         hull[k])) {
            k++;
        }
 
        double res = 0;
 
        // Check points from 0 to k
        for (int i = 0, j = k;
             i <= k && j < n; i++) {
            res = Math.max(res,
                           Math.sqrt((double)dist(hull[i],
                                                  hull[j])));
 
            while (j < n
                   && absArea(hull[i],
                              hull[(i + 1) % n],
                              hull[(j + 1) % n])
                          > absArea(hull[i],
                                    hull[(i + 1) % n],
                                    hull[j])) {
 
                // Update res
                res = Math.max(
                    res,
                    Math.sqrt(dist(hull[i],
                                   hull[(j + 1) % n])));
                j++;
            }
        }
 
        // Return the result distance
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Total points
        int n = 5;
        Point p[] = new Point[n];
 
        // Given Points
        p[0] = new Point(4, 0);
        p[1] = new Point(0, 2);
        p[2] = new Point(-1, -7);
        p[3] = new Point(1, 10);
        p[4] = new Point(2, -3);
 
        // Function Call
        System.out.println(rotatingCaliper(p));
    }
}

17.11724276862369

Complejidad de tiempo: O(N*log N)  
Espacio auxiliar: O(N)