Проверка вертикальной симметрии набора точек

30. Проверить вертикальную симметрию набора точек

Условие задачи:
Дан массив точек с целочисленными координатами (x, y).

Необходимо определить, существует ли вертикальная прямая x = c, относительно которой весь набор точек симметричен.

Для каждой точки (x, y), не лежащей на оси симметрии, должна существовать зеркальная точка (2c - x, y) с такой же кратностью.

Дубликаты точек необходимо учитывать.

Код:

public class SymmetryChecker {

    public static boolean isVertSym(int[][] points) {
        // TODO
    }
}

Примеры:

[[0, 0], [0, 1], [1, 1], [2, 2], [3, 1], [4, 1], [4, 0]] → true

[[0, 0], [0, 0], [1, 1], [2, 2], [3, 1], [4, 0], [4, 0]] → true

[[0, 0], [0, 0], [1, 1], [2, 2], [3, 1], [4, 0]] → false

[] → true

[[0, 0]] → true

[[0, 0], [10, 0]] → true

[[0, 0], [11, 1]] → false

[[0, 0], [1, 0], [3, 0]] → false

Спойлеры к решению

Подсказки

💡 Если симметрия существует, ось проходит ровно посередине между минимальным и максимальным x.
💡 Вместо самого c удобно хранить значение 2 * c = minX + maxX.
💡 Для каждой точки (x, y) зеркальная точка имеет координаты (minX + maxX - x, y).
💡 Используй Map<Point, Integer>, чтобы учитывать несколько одинаковых точек.
💡 Для суммы координат лучше использовать long, чтобы избежать переполнения int.

Решение

public static boolean isVertSym(int[][] points) {
    if (points.length <= 1) {
        return true;
    }

    int minX = Integer.MAX_VALUE;
    int maxX = Integer.MIN_VALUE;

    Map<Point, Integer> frequencies = new HashMap<>();

    for (int[] point : points) {
        int x = point[0];
        int y = point[1];

        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x);

        frequencies.merge(new Point(x, y), 1, Integer::sum);
    }

    long sum = (long) minX + maxX;

    for (Map.Entry<Point, Integer> entry : frequencies.entrySet()) {
        Point point = entry.getKey();

        long mirrorX = sum - point.x;

        if (mirrorX < Integer.MIN_VALUE
                || mirrorX > Integer.MAX_VALUE) {
            return false;
        }

        Point mirror = new Point((int) mirrorX, point.y);

        if (!Objects.equals(
                frequencies.get(mirror),
                entry.getValue()
        )) {
            return false;
        }
    }

    return true;
}

private static class Point {
    private final int x;
    private final int y;

    private Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (!(obj instanceof Point)) {
            return false;
        }

        Point other = (Point) obj;

        return x == other.x && y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Если ось симметрии существует, она определяется крайними точками по x.

Например:

minX = 0
maxX = 4

Тогда:

2 * c = minX + maxX = 4
c = 2

Для точки:

(0, 1)

зеркальная координата вычисляется как:

x' = 4 - 0 = 4

поэтому должна существовать точка:

(4, 1)

Для точки на самой оси:

(2, 2)

получится:

x' = 4 - 2 = 2

то есть она зеркальна сама себе.

Важно учитывать не только наличие зеркальной точки, но и количество её вхождений. Например:

(0, 0) — 2 раза
(4, 0) — 1 раз

не образуют симметричный набор.

Поэтому сравниваются частоты:

if (!Objects.equals(
        frequencies.get(mirror),
        entry.getValue()
)) {
    return false;
}

Временная сложность в среднем — O(n), дополнительная память — O(k), где k — количество различных точек.