Найти порямоугольников из списка координат

Question

У меня есть список координатов нужно найти кол-во получиться порямоугольников из этих координат

Я попробовал так

public static int countRectangles(List<Point> list) {
    int count = 0;

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

        int xCount = 0;
        int yCount = 0;

        for (int j = 0; j < list.size(); j++) {
            if (j != i) {
                if (list.get(i).x == list.get(j).x) {
                    xCount++;
                }
                if (list.get(i).y == list.get(j).y) {
                    yCount++;
                }
            }
            if (xCount >= 2 && yCount >= 2) {
                count++;
                break;
            }
        }
    }

    return count;
}

Но к сожалению не работает

Answer 1

Во-первых, чтобы перебрать все пары(не повторяясь!), вам нужно использовать следующую запись:

for(int i = 0; i < points.size(); i++){
        for(int b = i + 1; b < points.size(); b++){

Во-вторых, я бы создал специальную функцию, определяющую, образуют ли данные точки квадрат:

private static boolean isSquare(Point first, Point second){
    if(first.getX() == second.getX() || first.getY() == second.getY()){
        return false;
    }
    if(getDistanceBetween(first.getX(), second.getX()) == getDistanceBetween(first.getY(), second.getY())){
        return true;
    }
    return false;
}

public static int getDistanceBetween(int first, int second){ // Возможно, неоптимизированно, на скорую руку. O(3).
    if(first >= 0){
        if(second >= 0){
            return Math.abs(first - second);
        } else {
            return first - second;
        }
    } else {
        if(second >= 0){
            return second - first;
        } else {
            return Math.abs(first - second);
        }
    }
}

Хорошо, теперь у нас на руках есть все пары координат(лежащие напротив), которые образуют квадрат. Теперь нужно проверить, существуют ли другая пара координат:

public static boolean hasAnotherPairForSquare(Point first, Point second, List<Point> points){
    return points.contains(new Point(first.getX(), second.getY())) && points.contains(new Point(second.getX(), first.getY()));
}

Все. Осталось только посчитать кол-во таких пар, и поделить ее на двое. Тогда мы получим кол-во квадратов. Вот конечный код:

class Test {
    public static void main(String[] args) throws IOException {
        Tests.test1();
        Tests.test2();
        Tests.test3();
    }

    static class Tests{
        public final static String answerOutputTemplate;

        static{
            answerOutputTemplate = "sqCount: {0}. It is {1}";
        }

        public static void test1(){
            List<Point> points = List.of(new Point(1, 1), new Point(3, 3), new Point(3, 1), new Point(1, 3));
            int sqCount = getCountOfSq(points);
            System.out.println(MessageFormat.format(answerOutputTemplate, getCountOfSq(points), (sqCount == 1)));
        }
        public static void test2(){
            List<Point> points = List.of(new Point(-2, 4),
                                         new Point(2, 4),
                                         new Point(-2, -2),
                                         new Point(4, 7),
                                         new Point(2, 7),
                                         new Point(-2, 7),
                                         new Point(4, 4),
                                         new Point(4, -2),
                                         new Point(2, -2));
            int sqCount = getCountOfSq(points);
            System.out.println(MessageFormat.format(answerOutputTemplate, getCountOfSq(points), (sqCount == 1)));
        }
        public static void test3(){
            List<Point> points = List.of(new Point(-4, 3),
                                         new Point(-2, 1),
                                         new Point(-2, 2),
                                         new Point(-2, 5),
                                         new Point(-2, 6),
                                         new Point(0, 4),
                                         new Point(1, 2),
                                         new Point(3, 2),
                                         new Point(1, 5),
                                         new Point(3, 5),
                                         new Point(2, 0),
                                         new Point(4, 0),
                                         new Point(6, 3),
                                         new Point(2, -3),
                                         new Point(4, -3),
                                         new Point(0, 5),
                                         new Point(0, 2));
            int sqCount = getCountOfSq(points);
            System.out.println(MessageFormat.format(answerOutputTemplate, getCountOfSq(points), (sqCount == 2)));
        }

    }

    public static int getCountOfSq(List<Point> points){
        int pairsCounter = 0;
        for(int i = 0; i < points.size(); i++){
            for(int b = i + 1; b < points.size(); b++){
                if(isSquare(points.get(i), points.get(b)) && hasAnotherPairForSquare(points.get(i), points.get(b), points)){
                    pairsCounter++;
                }
            }
        }
        if(pairsCounter % 2 == 1){
            throw new Error("FATAL error");
        }
        return pairsCounter / 2;
    }

    public static boolean hasAnotherPairForSquare(Point first, Point second, List<Point> points){
        return points.contains(new Point(first.getX(), second.getY())) && points.contains(new Point(second.getX(), first.getY()));
    }

    private static boolean isSquare(Point first, Point second){
        if(first.getX() == second.getX() || first.getY() == second.getY()){
            return false;
        }
        if(getDistanceBetween(first.getX(), second.getX()) == getDistanceBetween(first.getY(), second.getY())){
            return true;
        }
        return false;
    }

    public static int getDistanceBetween(int first, int second){ // Возможно, неоптимизированно, на скорую руку. O(3).
        if(first >= 0){
            if(second >= 0){
                return Math.abs(first - second);
            } else {
                return first - second;
            }
        } else {
            if(second >= 0){
                return second - first;
            } else {
                return Math.abs(first - second);
            }
        }
    }

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

        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        int getX(){
            return x;
        }
        int getY(){
            return y;
        }

        @Override
        public boolean equals(Object o){
            if(o == null || !(o instanceof Point)){
                return false;
            }
            if(((Point) o).getX() == x && ((Point) o).getY() == y){
                return true;
            }
            return false;
        }

        @Override
        public String toString(){
            return "x: " + x + ", y: " + y;
        }
    }
}

Вывод:

sqCount: 1. It is true
sqCount: 1. It is true
sqCount: 2. It is true

Проверял на листочке - эти тесты верны.

БЛОГ НА HUSL

Найти порямоугольников из списка координат

Ответы (1 шт):