Страница 1 из 3 123 ПоследняяПоследняя
Показано с 1 по 20 из 50

Тема: Задачка для скучающих программистов.

  1. #1
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264

    Задачка для скучающих программистов.

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

    На вход подается таблица с размерами прямоугольников. в формате L H длинна и высота.

    найти такое размещение их на плоскости, чтобы суммарная площадь была минимальная. И вычислить какую площадь они в сумме занимают.

    То есть накладывая одни прямоугольники на другие найти такое наложение чтобы была минимальная площадь.

  2. #2
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    Может я чего-то не понимаю, но если прямоугольники накладывать друг на друга, то минимальная площадь будет достигаться, если совместить одни из углов (левый нижний, правый верхний, неважно) всех прямоугольников. И тогда бОльшие прямоугольники будут закрывать меньшие. Не?
    Последний раз редактировалось napancux; 25.03.2014 в 22:40.

  3. #3
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    napancux, Поворачивать их еще можно.

  4. #4
    Активный участник Аватар для Enta
    Регистрация
    17.05.2010
    Сообщений
    1,898
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    napancux, Поворачивать их еще можно.
    наркомания...
    поставил бы хоть 50р для затравки...

    а вообще первые 2 шага - совмещение крестом самого длинного и самого широкого (где ширина меньше длинны)
    Последний раз редактировалось Enta; 25.03.2014 в 22:55.
    Если в мире будет больше эгоистов - мир станет лучше.
    Когда к власти приходят сукины дети, собачья жизнь начинается у всех.

  5. #5
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    Спалланцани, у ты какой хитрый

  6. #6
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    Н только ан 90 гадусов поворачивать можно. Иначе наркомания начинается.

  7. #7
    Активный участник Аватар для explorer199
    Регистрация
    13.01.2011
    Сообщений
    420
    Поворачиваем все прямоугольники "длинной" стороной по одной оси, совмещаем левую верхнюю вершину, обводим. Опровержение?
    You spin me right round, baby
Right round like a record, baby
Right round, round, round

  8. #8
    Освоившийся Аватар для LuSaa
    Регистрация
    05.11.2011
    Сообщений
    228
    Если на 90 градусов поворачивать, то чушь какая-то, нет? Просто берешь самый большой, кладешь на него остальные и все?

  9. #9
    Новобранец
    Регистрация
    30.11.2012
    Сообщений
    94
    To Спалланцани:

    Условие задачи неполное. Есть два варианта интерпретации:

    1. Проекции прямоугольников могут пересекаться. Пример - прямоугольники из бумаги складываются в стопку. Тогда при условии L<=H общая площадь стопки не может превышать (MAX(L))^2.

    2. Проекции прямоугольников пересекаться не могут. Пример - складывание пустых коробок одна в другую. Тогда прямоугольник можно поместить в другой только при условии L1<=L2, H1<=H2. В таком случае общая площадь в худшем случае (ни одна коробка не помещается в другую) будет равна сумме площадей всех прямоугольников. В лучшем случае (все коробки матрешкой складываются одна в другую) общая площадь будет равна площади самого большого прямоугольника.

  10. #10
    Активный участник Аватар для Enta
    Регистрация
    17.05.2010
    Сообщений
    1,898
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    Н только ан 90 гадусов поворачивать можно. Иначе наркомания начинается.
    0. повернуть так чтоб длинна была больше ширины.
    1. отсортировать по длинне
    2. S = S1 + ... Sn
    S1 = A1*B1, Sn=An*(Bn-B(n-1)) при Bn>B(n-1) иначе Sn=0
    Если в мире будет больше эгоистов - мир станет лучше.
    Когда к власти приходят сукины дети, собачья жизнь начинается у всех.

  11. #11
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    LuSaa, прямоугольник может иметь очень большую высоту и очень маленькую ширину. Соответственно, всегда есть возможность, что что-то будет торчать.
    Последний раз редактировалось napancux; 25.03.2014 в 23:02.

  12. #12
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    explorer199, Напиши)

  13. #13
    Освоившийся Аватар для LuSaa
    Регистрация
    05.11.2011
    Сообщений
    228
    Цитата Сообщение от napancux Посмотреть сообщение
    LuSaa, прямоугольник может иметь очень большую высоту и очень маленькую ширину. Соответственно, всегда есть возможность, что что-то будет торчать.
    Ну вон, ребята уже нписали верное решение. Все равно задача слишком простая. Что-то тут не так.

  14. #14
    Активный участник Аватар для explorer199
    Регистрация
    13.01.2011
    Сообщений
    420
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    explorer199, Напиши)
    Программу? Тогда спецификацию ввода-вывода, чтобы потом не было споров по этому поводу.
    You spin me right round, baby
Right round like a record, baby
Right round, round, round

  15. #15
    Активный участник
    Регистрация
    26.02.2011
    Сообщений
    9,264
    Darij, Да могут пересекаться.

    - - - Добавлено - - -

    explorer199, Таблица прямоугольников. длинна ширина перенос строки. Конец файла в конце. На выходе площадь.

  16. #16
    Активный участник
    Регистрация
    11.08.2011
    Сообщений
    1,712
    Цитата Сообщение от Enta Посмотреть сообщение
    0. повернуть так чтоб длинна была больше ширины.
    1. отсортировать по длинне
    2. S = S1 + ... Sn
    S1 = A1*B1, Sn=An*(Bn-B(n-1)) при Bn>B(n-1) иначе Sn=0
    Bn должно быть больше не только B(n-1), но также и B(n-2) B(n-3) ... B1, иначе такая площадь уже учтена.

  17. #17
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    Цитата Сообщение от Спалланцани Посмотреть сообщение
    Н только ан 90 гадусов поворачивать можно. Иначе наркомания начинается.
    Ну так-то уже сказали.

    А я вот тут подумал, если поворачивать можно как угодно.

    1) Помещаем первый прямоугольник на условную плоскость;
    2) Помещаем следующий прямоугольник массива в центр первого;
    3) Сравниваем стороны, если (H2 && L2) > (H1 && L1) || (H2 && L2) < (H1 && L1), то ничего не делаем, так как прямоугольники покрывают друг друга;
    4) Далее, если H2 > H1 || L2 > L1, то поворачиваем новый прямоугольник таким образом, чтобы его центральная ось совпадала с диагональю уже помещенного прямоугольника, а центры прямоугольников совпадали;
    5) Все "повернутые" прямоугольники держим в переменной;
    6) Если появляется бОльший прямоугольник, то соответственно совмещаем все повернутые прямоугольники с новой диагональю.

    По идее это должно дать нужный результат. Но мне кажется, что есть и более эффективный метод. Ни это еще для случая, когда нам подают прямоугольники по одному, а не известна вся таблица целиком.
    Последний раз редактировалось napancux; 25.03.2014 в 23:13.

  18. #18
    Активный участник Аватар для Enta
    Регистрация
    17.05.2010
    Сообщений
    1,898
    Цитата Сообщение от cScDes Посмотреть сообщение
    Bn должно быть больше не только B(n-1), но также и B(n-2) B(n-3) ... B1, иначе такая площадь уже учтена.
    согласен.
    итого:
    0. повернуть так чтоб длинна была больше ширины.
    1. отсортировать по длинне
    2. S = S1 + ... Sn
    S1 = A1*B1, Sn=An*(Bn-MAX(B1 .. B(n-1))) при Bn>Bn-MAX(B1 .. B(n-1)) иначе Sn=0

    Был бы трезвее, написал бы SQL запрос...
    Последний раз редактировалось Enta; 25.03.2014 в 23:18.
    Если в мире будет больше эгоистов - мир станет лучше.
    Когда к власти приходят сукины дети, собачья жизнь начинается у всех.

  19. #19
    Активный участник Аватар для napancux
    Регистрация
    15.06.2010
    Сообщений
    631
    Цитата Сообщение от cScDes Посмотреть сообщение
    Bn должно быть больше не только B(n-1), но также и B(n-2) B(n-3) ... B1, иначе такая площадь уже учтена.
    А еще не обязательно добавляемая площадь при таком методе будет прямоугольником.

    Последний раз редактировалось napancux; 25.03.2014 в 23:25.

  20. #20
    Активный участник Аватар для explorer199
    Регистрация
    13.01.2011
    Сообщений
    420
    А, я думал, что нужно найти площадь прямоугольника, обводящего все эти прямоугольники
    Сами пишите, мне лень.
    You spin me right round, baby
Right round like a record, baby
Right round, round, round

Страница 1 из 3 123 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Задачка скучающего ботана №14(для программистов)
    от Спалланцани в разделе Общий форум
    Ответов: 25
    Последнее сообщение: 21.11.2013, 20:47
  2. Задачка скучающих ботанов № 13
    от Спалланцани в разделе Общий форум
    Ответов: 79
    Последнее сообщение: 14.11.2013, 14:04
  3. Задачка для скучающих ботанов №12
    от Спалланцани в разделе Общий форум
    Ответов: 20
    Последнее сообщение: 14.11.2013, 12:28
  4. Задачка для скучающих ботанов №10
    от Спалланцани в разделе Общий форум
    Ответов: 59
    Последнее сообщение: 12.11.2013, 21:42
  5. Задачка для скучающих ботанов №9
    от Спалланцани в разделе Общий форум
    Ответов: 82
    Последнее сообщение: 06.11.2013, 20:16

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •