HasVerticalSymLine.java

    /**
     * Вариант решения 1.
     * за линейное время. Использует память O(n)
     */
    boolean hasVerticalSymLine(int n, Point[] p) {
        //За линейное время могу пройти массив и найти максимум и минимум по x.
        int minX = p[0].x;
        int maxX = p[0].x;
        HashSet<Point> set = new HashSet<>(p.length);//Тут используем много памяти. Оценка O(n).
        for (int i = 0; i < p.length; i++) {
            if (minX > p[i].x) minX = p[i].x;
            if (maxX < p[i].x) maxX = p[i].x;
            set.add(p[i]);
        }
        int avgDoubled = minX + maxX;//предполагаемая координата X вертикальной прямой, умноженная на два
        //перебираем все левые точки и ищем пару. Оценка линейна, так как в хеш таблице ищем за константу
        for (int i = 0; i < p.length; i++) {
            if (p[i].x * 2 <= avgDoubled && !set.contains(new Point(avgDoubled - p[i].x, p[i].y)))
                return false;
        }
        return true;
    }

    /**
     * Вариант решения 2.
     * если точек очень много и они не помещаются на одну машину
     * сложность O(n^2). Дополнительно память не трубует.
     * Работает медленно
     */
    boolean hasVerticalSymLineBig(int n, Point[] p) {
        //За линейное время могу пройти потоком и найти максимум и минимум по x.
        int minX = p[0].x;
        int maxX = p[0].x;
        for (int i = 0; i < p.length; i++) {
            if (minX > p[i].x) minX = p[i].x;
            if (maxX < p[i].x) maxX = p[i].x;
        }
        int avgDoubled = minX + maxX;//предполагаемая координата X вертикальной прямой, умноженная на два
        //перебираем все точки левее прямой и ищем пару. Оценка квадратична
        //открываем два потока файла на чтение
        for (int i = 0; i < p.length; i++) {
            if (p[i].x * 2 <= avgDoubled) {
                boolean pairExists = false;
                for (int j = 0; j < p.length; j++)
                    if (i != j && p[i].y == p[j].y
                            && avgDoubled - p[i].x == p[j].x)//правая точка = x + (координата прямой - x)*2
                        pairExists = true;
                if (!pairExists)
                    return false;
            }
        }
        return true;
    }

    /**
     * Вариант решения 3.
     * Если в процессе добавления точек их можно было сразу сортировать по координате x.
     * Тогда одна операция добавления занимала бы время O(log(n)) вместо константного
     * Или перед вызовом функции проверки отсортировать список с помощью merge sort за n*log(n)
     * тогда сама функция будет работать за линейное время.
     * Предполагаю, что могу читать файл в два потока с конца и с начала.
     * Для этого алгоритма координата x должна быть уникальна,
     * или структура допускать хранение для координаты х списка y и этот список помещается в память одной машины.
     */
    boolean hasVerticalSymLinePresorted(int n, Point[] p) {
        int avgDoubled = p[0].x + p[p.length - 1].x;//предполагаемая координата X вертикальной прямой, умноженная на два
        for (int i = 0; i < p.length / 2; i++) {
            Point left = p[i];
            Point right = p[p.length - i - 1];
            if (left.y != right.y)
                return false;
            if (left.x + avgDoubled - left.x * 2 != right.x)
                return false;
        }
        return true;
    }