Определить координаты противоположных углов прямоугольника – левого нижнего и верхнего правого в одномерном массиве?

Question

[Arsenikum]

На плоскости даны 20 точек (x1,y1), (x2,y2)…(x20,y20). Рассмотрим наименьший прямоугольник, содержащий эти точки со сторонами, параллельными координатным осям. Определить координаты противоположных углов этого прямоугольника – левого нижнего и верхнего правого.

Comments

[sim3x]

только из уважения к ответам данный вопрос не удален сразу

Answer 1

[TomasHuk]

Если я правильно понял, то координаты искомых точек прямоугольника это точки (min_X, min_Y) - минимальные координаты X и Y среди всех точек, а (max_X, max_Y) - аналогично.

coords = [(10,12),(8,6),(9,12),(9,9),(13,13)]
all_x = []
all_y = []
for coord in coords:
    all_x.append(coord[0])
    all_y.append(coord[1])

first_point = (min(all_x), min(all_y))
second_point = (max(all_x), max(all_y))
print(first_point)
print(second_point)

Comments

[Arsenikum]

немного не правильно, если допустим будет точка (7,7) то ответ для минимума будет (7,6), а такого прямоугольника нет

[Arsenikum]

TomashUA, вообще надо найти наименьший из них, и лишь потом определять его координаты

[TomasHuk]

В вопросе написано "наименьший прямоугольник, содержащий эти точки". Можно подумать, что все эти точки.

Answer 2

[Максим Васильев]

left = min([ p[0] for p in points ])
right = max([ p[0] for p in points ])
top = min([ p[1] for p in points ])
bottom = max([ p[1] for p in points ])

Если точек слишком дофига, то эффективнее будет в один проход:

left = float("+Inf")
right = float("-Inf")
top = float("+Inf")
bottom = float("-Inf")
for p in points:
    left = min(left, p[0])
    right = max(right, p[0])
    top = min(left, p[1])
    bottom = max(right, p[1])

Comments

[Максим Васильев]

Ой, ну тоесть это для координат свеху, а не снизу как у вас.

Answer 3

[DaneSoul]

1) Не забываем условие, что стороны прямоугольника паралельны координатным осям - это возможно только в случае, когда у нас для 4-х точек (x1,y1), (x2,y2), (x3,y3), (x4,y4) выполняются сразу 4 условия:
x1=x2, x3=x4, y1=y3, y2=y4

2) Выбираем все уникальные х-координаты, которые представлены более чем в 1 экземпляре - это набор прямых проходящий через точки нашего набора параллельно оси Oy.
Для этих прямых выбираем все точки из исходного списка, которые на них лежат.

3) По аналогии с пунктом 2 делаем тоже самое для y

4) В итоге, мы имеем два набора точек - один рассчитанный в пункте 2 и второй в пункте 3, причем, сразу заметим, что часть точек присутствуют в обеих, а часть только в одном из них и эту вторую часть можно будет сразу отбросить, так как они не находятся на пересечении прямых.

5) Дальше используя комбинаторику перебираем все варианты пар точек по горизонтали и аналогичный по вертикали, считая площади, не забывая проверять пункт 1.
Вот этот пункт самый ресурсоёмкий и его можно оптимизировать.

6) Площади считаем из координат по простой формуле: S = (x3-x1) * (y2-y1)