Как найти максимальное расстояние между точками

import java.awt.*;

import java.util.*;

import java.util.Map.Entry;

public class Main {

    static int orientation(Point p,

                           Point q,

                           Point r)

    {

        int x = area(p, q, r);

        if (x > 0) {

            return 1;

        }

        if (x < 0) {

            return -1;

        }

        return 0;

    }

    static int area(Point p, Point q, Point r)

    {

        return ((p.y - q.y) * (q.x - r.x)

                - (q.y - r.y) * (p.x - q.x));

    }

    static int absArea(Point p,

                       Point q, Point r)

    {

        return Math.abs(area(p, q, r));

    }

    static int dist(Point p1, Point p2)

    {

        return ((p1.x - p2.x) * (p1.x - p2.x)

                + (p1.y - p2.y) * (p1.y - p2.y));

    }

    static ArrayList<Point>

    convexHull(Point points[])

    {

        int n = points.length;

        Point min = new Point(Integer.MAX_VALUE,

                              Integer.MAX_VALUE);

        int ind = -1;

        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;

        Arrays.sort(points, 1, n,

                    new Comparator<Point>() {

                        @Override

                        public int compare(Point o1,

                                           Point o2)

                        {

                            int o = orientation(min, o1, o2);

                            if (o == 0) {

                                return dist(o1, min)

                                    - dist(o2, min);

                            }

                            if (o == 1) {

                                return 1;

                            }

                            return -1;

                        }

                    });

        Stack<Point> st = new Stack<>();

        st.push(points[0]);

        int k;

        for (k = 1; k < n - 1; k++) {

            if (orientation(points[0],

                            points[k],

                            points[k + 1])

                != 0)

                break;

        }

        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<>();

        for (int i = 0; i < st.size(); i++) {

            hull.add(st.get(i));

        }

        return hull;

    }

    static double

    rotatingCaliper(Point points[])

    {

        ArrayList<Point> convexHull

            = convexHull(points);

        int n = convexHull.size();

        Point hull[] = new Point[n];

        n = 0;

        while (n < convexHull.size()) {

            hull[n] = convexHull.get(n++);

        }

        if (n == 1)

            return 0;

        if (n == 2)

            return Math.sqrt(dist(hull[0], hull[1]));

        int k = 1;

        while (absArea(hull[n - 1],

                       hull[0],

                       hull[(k + 1) % n])

               > absArea(hull[n - 1],

                         hull[0],

                         hull[k])) {

            k++;

        }

        double res = 0;

        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])) {

                res = Math.max(

                    res,

                    Math.sqrt(dist(hull[i],

                                   hull[(j + 1) % n])));

                j++;

            }

        }

        return res;

    }

    public static void main(String[] args)

    {

        int n = 5;

        Point p[] = new Point[n];

        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);

        System.out.println(rotatingCaliper(p));

    }

}

Найти наибольшее расстояние между точками

21.01.2012, 06:47. Показов 5071. Ответов 13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<math.h>
 
float maxspacing (int x, int y, int n1, int i1, int j1, int &rT1, int &rT2)
{
      float space=0, d=0;
      for (i1=0; i1<n1-1; i1++)
      {
          for (j1=i1+1; j1<n1-2; j1++)
          {
              d=sqrt((x[i1]-x[j1])*(x[i1]-x[i1]) + (y[i1]-y[j1])*(y[i1]-y[j1]));
              if (d>space)
              {
                 space=d;
                 rT1=i1;
                 rT2=j1;
              }  
              d=0;
          }
      }
      
      return space;
}
                     
int main()
{
    int i, j, n, t1, t2;
    float sp=0, d=0;  
    int koordx[n];
    int koordy[n];
    
    std::cout << "vvedite kolichestvo tochek: ";
    std::cin >> n;
    std::cout << "nn";
    
    for (i=0; i<n; i++)
    {
        j=i+1;
        std::cout << "zadaite koordinatu x " << j << "-i tochki: ";
        std::cin >> koordx[i];
    }
    
    std::cout << "nn";
    
    for (i=0; i<n; i++)
    {
        j=i+1;
        std::cout << "zadaite koordinatu y " << j << "-i tochki: ";
        std::cin >> koordy[i];
    }
    
    sp = maxspacing (koordx, koordy, n, i, j, t1, t2);
    
    std::cout << "max rasstoyanie mezhdu tochkami s koordinatami:n";
    std::cout << "(" << koordx[t1] << "; " << koordy[t1] << ") i (";
    std::cout << koordx[t2] << "; " << koordy[t2] << ")";
    
    system("pause");
}

0

У меня есть список L из точек (x, y) и обычная евклидова мера расстояния

Как найти максимальное расстояние между двумя точками в этом списке? Или, более формально: как мне найти

Тривиальный подход

Самый простой способ решить эту проблему – попробовать все:

def find_max_dist(L):
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        for j in range(i+1, len(L):
            max_dist = max(d(L[i], L[j]), max_dist)
    return max_dist

Чтобы ускорить вычисления, я могу использовать квадратное расстояние в циклах и вернуть корень в конце.

Этот подход имеет сложность во время выполнения где n длина списка L, (И постоянная космическая сложность).

Выпуклый корпус

Очевидно, что не может быть алгоритма, который работает быстрее, чем O(n), так как нужно хотя бы один раз посмотреть на каждый элемент в списке.

Наибольшее расстояние будет между элементами выпуклой оболочки. Но легко доказать, что вычисление выпуклой оболочки по крайней мере в O(n log n) и сканирование Грэма, кажется, делает это. Но после нахождения сложного корпуса мне все равно нужно пройти максимальное расстояние. Так что я бы в конечном итоге

def find_max_dist_graham_triv(L):
    H = Graham_scan(L)
    return find_max_dist(L)

Это точка, в которой я не уверен. Я думаю, что можно улучшить это так:

def find_max_dist_graham_c1(L):
    H = Graham_scan(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        loop_max_dist = 0
        for j in range(i+1, len(L):
            curr_dist = d(L[i], L[j])
            if curr_dist < loop_max_dist:
                break
            loop_max_dist = curr_dist
            max_dist = max(loop_max_dist, max_dist)

    return max_dist

Идея состоит в том, что когда вы берете одну точку выпуклой оболочки и начинаете с соседней точки, диагонали продолжают увеличиваться, доходят до максимума, а затем продолжают уменьшаться. Хотя я не уверен, правда ли это.

Интуитивно понятно, что я бы продолжил улучшать алгоритм: как только закончится первый внутренний цикл, мы нашли “самую длинную диагональ” этого цикла. Эта диагональ разделяет все остальные точки корпуса на два несвязных множества. Каждая более длинная диагональ должна состоять из точек обоих этих наборов (правильно?):

def find_max_dist_graham_c1(L):
    H = Graham_scan(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])  # Get a fist idea what the longest distance might be

    i = 0
    p1 = L[i]  # Grab a random point
    loop_max_dist = 0
    for j in range(1, len(L):
        curr_dist = d(L[i], L[j])
        if curr_dist < loop_max_dist:
            break
        loop_max_dist = curr_dist
        max_dist = max(loop_max_dist, max_dist)
    # Every diagonal that is longer than the best one found with L[0]
    # has to have points in both of the following two sets (correct?):
    # [1...j] and [j+1...len(L)]

    # Try to find a neighboring diagonal that is longer.
    change = True
    while change:
        change = False
        if d(L[i-1], L[j+1]) > max_dist:
            max_dist = d(L[i-1], L[j+1])
            i -= 1
            j += 1
            change = True
        elif d(L[i+1], L[j-1]) > max_dist:
            max_dist = d(L[i+1], L[j-1])
            i += 1
            j -= 1
            change = True
    return max_dist

Каждая точка P на выпуклой оболочке имеет точку Q на выпуклой оболочке, так что PQ является самой длинной диагональю, включая P. Но тогда P также является “конечной точкой” для самой длинной диагонали Q?

Я действительно не уверен, что этот алгоритм правильный. Это было бы в O(n log n).

Я думаю, что проблема хорошо проанализирована, так что, может, кто-нибудь оставит несколько заметок для этого?

Хотя у меня было много подвопросов, главный вопрос:

Как эффективно найти максимальное расстояние между точками в списке точек?

Максимальное расстояние равно 35 (длина наборов). Найдём, сколькими способами можно этого добиться.

Сравним разряды строк попарно. Окажется, что имеется 7 разрядов типа (0,0) для $%alpha$% и $%beta$% соответственно; 5 разрядов типа (0,1); 10 разрядов типа (1,0), и 13 разрядов типа (1,1). Для того, чтобы изменённые наборы различались во всех 35 позициях, необходимо и достаточно следующее. Если разряды первой группы типа (0,0) мы меняем у $%alpha$% в количестве $%x$%, то у $%beta$% мы меняем остальные $%7-x$% из этих семи разрядов. У второй группы (0,1) мы должны там и там сменить одни и те же $%yge0$% разрядов. Для третьей группы (1,0) меняем там и там одни и те же $%zge0$% разрядов. Наконец, для четвёртой группы (1,1) мы меняем какие-то $%t$% разрядов у $%alpha$% и оставшиеся $%13-t$% разрядов у $%beta$%. При этом должны выполняться равенства $%x+y+z+t=15$% и $%7-x+y+z+13-t=13$%, что означает $%x+t=11$% и $%y+z=4$%.

Таким образом, нам нужно из 20 разрядов типа (0,0) и (1,1) выбрать какие-то 11, а также из 15 разрядов типа (0,1) и (1,0) выбрать какие-то 4. Этот выбор всё однозначно определяет. Наборы после изменений оказываются противоположными, и расстояние между ними равно 35. Сделать их такими можно $%C_{20}^9cdot C_{15}^4$% способами.

Добавление. Вот пример, когда у $%alpha$% сменили 15 разрядов, у $%beta$% сменили 13, и получили противоположные наборы $%alpha’$% и $%beta’$% на расстоянии 35:

$%11111101011111110001111010100011010$% ($%alpha$%)

$%10100010010010100101111011001001010$% ($%alpha’$%)

$%01011111001101010100000001101011110$% ($%beta$%)

$%01011101101101011010000100110110101$% ($%beta’$%)