Найти прямоугольник, который лежит внутри максимального кол-ва других прямоугольников

@koly121121 · Регистрация: 14.10.2017

Студворк — интернет-сервис помощи студентам

Для набора прямоугольников, стороны которых параллельны OX и OY, заданных координатами 2-х диагональных вершин, найти прямоугольник, который лежит внутри максимального кол-ва других прямоугольников (граница вложенного прямоугольника

может проходить по границе внешнего прямоугольника). В случае существования нескольких подходящих прямоугольников – выбрать минимального периметра (если и таких будет несколько – то произвольный). ДЛЯ PYTHON ПОЖАЛУЙСТА.

@ТабуретY · 11.03.2018, 17:59

Так, но надо проверить

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from random import randint
import copy
 
#Фунция проверяет находится ли прямоугольник в прямоугольнике
def contains(r1, r2):
    return r1[0][0] <= r2[0][0] <= r2[1][0] <= r1[1][0] and r1[0][1] >= r2[0][1] >= r2[1][1] >= r1[1][1]
 
#Тут генерируется список случайных прямоугольников
first_diagonal_points = [(92, 15), (42, 52), (80, 22), (64, 94), (89, 45), (51, 91), (26, 51), (91, 89), (95, 21), (95, 56), (50, 44), (96, 50), (93, 89), (49, 54), (52, 86), (12, 71), (93, 58), (53, 70), (89, 99), (52, 91), (38, 32), (87, 37), (42, 30), (15, 15), (23, 67), (29, 56), (28, 21), (76, 77), (62, 46), (27, 50), (88, 54), (74, 86), (52, 25), (67, 66), (98, 78), (30, 71), (96, 52), (89, 13), (81, 64), (97, 56), (99, 73), (77, 10), (51, 25), (25, 55), (48, 15), (10, 91), (45, 12), (85, 61), (53, 62), (22, 69)]
 
rects = []
for x in first_diagonal_points:
    a,b = randint(0,x[0]), randint(0,x[1])
    rects.append(((a,x[1]), (x[0],b)))
#----------------------------------------------------
rects_dup = copy.copy(rects)
 
dists = {}
 
for x in rects:
    rects_dup.remove(x)
    for y in rects_dup:
        if contains(y,x):
            if x in dists.keys():
                dists[x] += 1
            else:
                dists[x] = 1
 
max_value = max(dists.values())
max_keys = [k for k, v in dists.items() if v == max_value]
 
max_key = sorted(max_keys, key=lambda x: (x[0][0]-x[1][0], x[1][0]-x[1][1]))[0]
 
print(max_value, max_key)

Добавлено через 1 час 19 минут
Исправленная версия

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from random import randint
import copy
 
#Фунция проверяет находится ли прямоугольник в прямоугольнике
def contains(r1, r2):
    return r1[0][0] <= r2[0][0] <= r2[1][0] <= r1[1][0] and r1[0][1] >= r2[0][1] >= r2[1][1] >= r1[1][1]
 
#Тут генерируется список случайных прямоугольников
first_diagonal_points = [(92, 15), (42, 52), (80, 22), (64, 94), (89, 45), (51, 91), (26, 51), (91, 89), (95, 21), (95, 56), (50, 44), (96, 50), (93, 89), (49, 54), (52, 86), (12, 71), (93, 58), (53, 70), (89, 99), (52, 91), (38, 32), (87, 37), (42, 30), (15, 15), (23, 67), (29, 56), (28, 21), (76, 77), (62, 46), (27, 50), (88, 54), (74, 86), (52, 25), (67, 66), (98, 78), (30, 71), (96, 52), (89, 13), (81, 64), (97, 56), (99, 73), (77, 10), (51, 25), (25, 55), (48, 15), (10, 91), (45, 12), (85, 61), (53, 62), (22, 69)]
 
rects = []
for x in first_diagonal_points:
    a,b = randint(0,x[0]), randint(0,x[1])
    rects.append(((a,x[1]), (x[0],b)))
#----------------------------------------------------
dists = {}
 
for x in rects:
    for y in rects:
        if x != y:
            if contains(y,x):
                if x in dists.keys():
                    dists[x] += 1
                else:
                    dists[x] = 1
 
max_value = max(dists.values())
max_keys = [k for k, v in dists.items() if v == max_value]
 
max_key = sorted(max_keys, key=lambda x: (x[0][0]-x[1][0], x[1][0]-x[1][1]), reverse=True)[0]
 
print(max_value, max_key)

@koly121121 · 11.03.2018, 18:06 **[ТС]**

ТабуретY, можете, пожалуйста, объяснить эти строчки

Python
1
2
3
4
max_value = max(dists.values())
max_keys = [k for k, v in dists.items() if v == max_value]
 
max_key = sorted(max_keys, key=lambda x: (x[0][0]-x[1][0], x[1][0]-x[1][1]))[0]

@ТабуретY · 11.03.2018, 18:17

Python
1
2
3
4
5
6
7
8
9
#Находим максимальное значение
max_value = max(dists.values())
 
#Так как максимальное значение может быть не одно, то находим все элементы с максимальным значением
max_keys = [k for k, v in dists.items() if v == max_value]
 
#Так как по заданию нужно выбрать прямоугольник с минимальной диагональю, 
#то сортируем по размеру диагонали и берем первый
max_key = sorted(max_keys, key=lambda x: (x[0][0]-x[1][0], x[1][0]-x[1][1]))[0]

@orAnd · 11.03.2018, 19:04

ТабуретY, мне кажется, что последнюю строчку лучше переписать с использованием функции min - она тоже может принимать аргумент key.

@ТабуретY · 11.03.2018, 19:14

Сообщение от orAnd

последнюю строчку лучше переписать с использованием функции min

Это, конечно, лучший вариант

Новые блоги и статьи Все статьи Все блоги /
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .

@koly121121 0 / 0 / 0 Регистрация: 14.10.2017 Сообщений: 14

	Найти прямоугольник, который лежит внутри максимального кол-ва других прямоугольников 11.03.2018, 09:41. Показов 4405. Ответов 5 Метки нет (Все метки) Для набора прямоугольников, стороны которых параллельны OX и OY, заданных координатами 2-х диагональных вершин, найти прямоугольник, который лежит внутри максимального кол-ва других прямоугольников (граница вложенного прямоугольника может проходить по границе внешнего прямоугольника). В случае существования нескольких подходящих прямоугольников – выбрать минимального периметра (если и таких будет несколько – то произвольный). ДЛЯ PYTHON ПОЖАЛУЙСТА. 0

@orAnd 119 / 103 / 53 Регистрация: 13.04.2014 Сообщений: 233
	11.03.2018, 19:04
	ТабуретY, мне кажется, что последнюю строчку лучше переписать с использованием функции min - она тоже может принимать аргумент key. 1

Опции темы