Подсчитать количество квадратов из набора вершин, C ++

Question

У меня есть C ++ код для подсчета, сколько квадратов можно сформировать из заданного набора точек с координатами X, Y. Пример ввода на 5 баллов выглядит так:

5
0 0
0 2
1 0
2 0
2 2

Одно важное замечание: квадраты не обязательно должны быть выровнены по оси. Вот рабочий код, взятый из codechef.com:

int N = 5;
std::vector<int> arr_x{0, 0, 1, 2, 2};
std::vector<int> arr_y{0, 2, 0, 0, 2};

int flag1 = 0;
int flag2 = 0;
int count = 0;
for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        flag1 = 0;
        flag2 = 0;
        int x1 = arr_x[i], y1 = arr_y[i];
        int x2 = arr_x[j], y2 = arr_y[j];

        int p1_x = x1 - y1 + x2 + y2;
        int p2_x = x1 + y1 + x2 - y2;
        int p1_y = x1 + y1 - x2 + y2;
        int p2_y = -x1 + y1 + x2 + y2;

        for (int k = 0; k < N; k++) {
            if (2 * arr_x[k] == p1_x && 2 * arr_y[k] == p1_y) {
                flag1 = 1;
            }
            if (2 * arr_x[k] == p2_x && 2 * arr_y[k] == p2_y) {
                flag2 = 1;
            }
        }
        if (flag1 && flag2) count++;
    }
}
std::cout << count / 2 << std::endl;

Я не понимаю логику и значение p1_x, p2_x, p1_y, p2_y. Если кто-то может дать мне объяснение, пожалуйста, сделайте это.

Answer 1

Первый цикл

for (int i = 0; i < N; i++) {

повторяется по всем вершинам.Второй цикл

    for (int j = i + 1; j < N; j++) {

повторяется по всем вершинам после i.Алгоритм предполагает, что вершины являются противоположными углами, и вычисляет две пропущенные вершины.

        int p1_x = x1 - y1 + x2 + y2;
        int p2_x = x1 + y1 + x2 - y2;
        int p1_y = x1 + y1 - x2 + y2;
        int p2_y = -x1 + y1 + x2 + y2;

Вычисление не совсем корректно, чтобы избежать арифметики с плавающей запятой.Это должно быть, например, (x1 - y1 + x2 + y2) / 2.Позже вершины умножаются на 2, чтобы исправить это.В последнем цикле

        for (int k = 0; k < N; k++) {

ищутся две отсутствующие вершины.Флаг устанавливается, если найдена вершина.

            if (2 * arr_x[k] == p1_x && 2 * arr_y[k] == p1_y) {
                flag1 = 1;
            }
            if (2 * arr_x[k] == p2_x && 2 * arr_y[k] == p2_y) {
                flag2 = 1;
            }
        }

Если найдены обе пропущенные вершины, этот квадрат считается.

        if (flag1 && flag2) count++;
    }
}

Поскольку каждый квадрат подсчитывается вдвое, числоделится на два.

std::cout << count / 2 << std::endl;

Пример для вычисления:

Вершина 1 равна (0, 0).Вершина 2 - это (2, 0).Тогда обе недостающие вершины - (1, 1) и (1, -1).Давайте попробуем вычисление:

p1_x = (0 - 0 + 2 + 0) / 2 = 1
p2_x = (0 + 0 + 2 - 0) / 2 = 1
p1_y = (0 + 0 - 2 + 0) / 2 = -1
p2_y = (0 + 0 + 2 + 0) / 2 = 1

В результате получим две пропущенные вершины.