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:
C++
#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
Java
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));
}
}
Python3
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
C#
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
Javascript
<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>
Producción:
17.11724276862369
Complejidad Temporal: O(N 2 ), 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:
- 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.
- 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.
- 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.
- 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
// 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));
}
}
Producción:
17.11724276862369
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por adarsh000321 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA