• ,

Кухня(); Задание N69


Правила
[Одномерные массивы]
69. В одномерном массиве с четным количеством элементов (2N) находятся координаты N точек плоскости. Они располагаются в следующем порядке: x1, y1, х2, y2, x3, y3, и т.д. Найти номера самых удаленных друг от друга точек и наименее удаленных друг от друга точек.

Перед тем как постить код,
Порасспрашивал народ.
Как красиво написать,
Что бы в кайф было читать?!

Ctrl Alt L — Reformat Code
Run и пост готов, вперед!
Что еще вам нужно знать,
Не забудьте рассказать!:)

5 комментариев

Vash_the_Stampede
public static void solve(double[] arr) {
    int n = arr.length / 2;
    ArrayList<Point> points = new ArrayList<>(n);
    ArrayList<Segment> segments = new ArrayList<>((n * n - n) / 2);

    for (int i = 0; i < n; i++) {
        points.add(new Point(i, arr[2 * i], arr[2 * i + 1]));
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            segments.add(new Segment(points.get(i), points.get(j)));
    }

    Comparator<Segment> isShorter = new Comparator<Segment>() {
        @Override
        public int compare(Segment o1, Segment o2) {
            if (o1.getLength() < o2.getLength())
                return 1;
            if (o1.getLength() > o2.getLength())
                return -1;
            return 0;
        }
    };
    Comparator<Segment> isLonger = isShorter.reversed();

    Segment theShortestSegment = Algorithm.find(segments, isShorter);
    Segment theLongestSegment = Algorithm.find(segments, isLonger);

    // номера наименее удаленных точек
    int min1 = theShortestSegment.a.id;
    int min2 = theShortestSegment.b.id;

    // номера наиболее удаленных точек
    int max1 = theLongestSegment.a.id;
    int max2 = theLongestSegment.b.id;
}

static class Point {
    public final int id;
    public final double x, y;

    public Point(int id, double x, double y) {
        this.id = id;
        this.x = x;
        this.y = y;
    }

    public double distanceTo(Point p) {
        return Math.hypot(x - p.x, y - p.y);
    }
}

static class Segment {
    public final Point a, b;
    private Double length;

    public Segment(Point a, Point b) {
        this.a = a;
        this.b = b;
    }

    public Double getLength() {
        if (length == null)
            length = a.distanceTo(b);
        return length;
    }
}

static class Algorithm {
    private Algorithm() {
    }

    static <T> T find(List<T> list, Comparator<T> comparator) {
        T result;

        if (list == null) {
            return null;
        }

        result = list.get(0);

        for (T t : list) {
            if (t == null)
                continue;

            if (result == null) {
                result = t;
                continue;
            }

            if (comparator.compare(result, t) > 0)
                result = t;
        }

        return result;
    }
}
Vash_the_Stampede
борщанул?
LastLost
ну поиск мин-мах — в один цикл и один вложенный. Перебор через 2 индекса. Не?
Docktor91
действительно, к чему эти колящие глаза куча букв))))
Airon
Вообще все нормально, но вот, чтобы я изменил:
static <T> T find(List<T> list, Comparator<T> comparator) {
    if (list == null)
        return null;
    T result = null;   
    for (T t : list) {
   //...
}

Comparator<Segment> isShorter = new Comparator<Segment>() {
    @Override
    public int compare(Segment o1, Segment o2) {
        return o1.getLength() - o2.getLength();
    }
};
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.