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

Для каждой пары точек, скажем, (x1, y1) и (x2, y2), считайте ее диагональю некоторого прямоугольника. Если в исходном множестве есть точки (x1, y2) и (x2, y1), то мы нашли наш прямоугольник. Следует отметить, что будут существовать 2 диагонали, которые будут представлять один и тот же прямоугольник, поэтому мы делим окончательный ответ на 2.

Это будет работать только для прямоугольников, параллельных оси x или оси y.

Псевдокод С++:

answer = 0;
set<pair<int, int>> points;

for(auto i=points.begin(); i!=std::prev(points.end()); i++)
{
    for(auto j=i+1; j!=points.end(); j++)
    {
        pair<int, int> p1 = *i;
        pair<int, int> p2 = *j;

        if(p1.first == p2.first || p1.second == p2.second)
            continue;

        pair<int, int> p3 = make_pair(p1.first, p2.second);
        pair<int, int> p4 = make_pair(p2.first, p1.second);

        if(points.find(p3) != points.end() && points.find(p4) != points.end())
            ++answer;
    }
}

return answer/2;

Разделите свои точки в списках координаты «y», сгруппированных по координате «x». В вашем случае у вас будет два отсортированных списка:

3: [0,4,6,8,10]
6: [0,4,8,10]

Выполняя пересечение обоих списков, вы получаете: [0,4,8,10]

Любые два из них образуют прямоугольник:

[0,4] => (3,0), (3,4), (6,0), (6,4)
[0,8] => (3,0), (3,8), (6,0), (6,8)
[4,8] => (3,4), (3,8), (6,4), (6,8)
...

Это решение работает только для ортогональных прямоугольников, то есть со сторонами, параллельными оси x, y.

Чтобы проверить, образуют ли 4 точки прямоугольник:

1. для каждых двух точек рассчитайте расстояние. хранить все в массиве поплавков.
2. отсортировать массив.

у вас будет a[0] = a[1], a[2] = a[3], a[4] = a[5]

Как я могу найти, образуют ли следующие координаты прямоугольник

Проверьте, являются ли разностные векторы ортогональными, т.е. имеют нулевое скалярное произведение.

Это не проверяет, включены ли эти координаты в ваш список. Он также не проверяет, выровнен ли прямоугольник с осями координат, что было бы гораздо более простой задачей.

Если вы хотите найти все прямоугольники во входных данных, вы можете выполнить описанную выше проверку для всех четверок. Если это неприемлемо по соображениям производительности, вам следует обновить свой вопрос, указав, с каким размером проблемы и ограничениями производительности вы сталкиваетесь.

Моя скромная покорность

Я предполагаю, что количество оптимизаций возможно.

Мой подход заключается в

• Пройтись по каждой точке
• Проверьте, какие все точки находятся прямо над этой точкой, а затем сохраните координаты Y этих точек, которые образуют линию.
• В следующий раз, когда я снова найду ту же координату Y, это означает, что мы нашли 1 прямоугольник
• Продолжайте снова проходить все остальные точки, делая то же самое.

Мое решение выполняется за O(n^2), но это будет только прямоугольник, параллельный оси X или Y.

Вот мой код для вышеуказанного подхода:

def getRectangleCount(coordinate):
    n = len(coordinate)
    y_count = dict()
    ans = 0
    for i in range(n):
        x, y = coordinate[i]
        for j in range(n):
            dx = coordinate[j][0]
            dy = coordinate[j][1]
            if y < dy and x == dx:
                ans += y_count.get((y, dy), 0)
                y_count[(y, dy)] = y_count.get((y, dy), 0) + 1
    return ans


coordinate = [[3, 10], [3, 8], [3, 6], [3, 4], [3, 0], [6, 0], [6, 4], [6, 8], [6, 10]]
print(getRectangleCount(coordinate))