|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Нет наработок или кода, если нужно готовое решение - создайте тему в разделе Фриланс и оплатите работу. Название темы включает слова - "Помогите", "Нужна помощь", "Срочно", "Пожалуйста". Название темы слишком короткое или не отражает сути вашего вопроса. Тема исчерпала себя, помните, один вопрос - одна тема Прочитайте правила и заново правильно создайте тему. |
|
Опции темы | Поиск в этой теме |
16.04.2011, 20:45 | #1 |
Пользователь
Регистрация: 29.01.2009
Сообщений: 60
|
Ось с прямоугольниками, найти общую площадь
Дана ось на которой множество прямоугольников, найти площадь фигуры образованной ими. Для ясности вот картинка, толстой линией выделена интересующая фигура http://pikucha.ru/i4NK2
Картинка примерна и на практике в программе прямоугольники могут быть в разном количестве, размере и месте Последний раз редактировалось sp.caster; 16.04.2011 в 20:50. |
16.04.2011, 21:33 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
1) сортируете все прямоугольники по координатам левых сторон.
2) в цикле от самой левой вертикальной границы до самой правой. находите участок до ближайшей (вправо) вертикальной границы. находите максимальную высоту (т.к. в найденном промежутке внутри нет границ, значит изменений высок тоже нет. умножаем высоту на длину найденного участка. прибавляем к общей сумме (общая площадь). повторяем в цикле. всё. Добавлено а ещё можно решить задачу "в лоб": выбрать минимальный шаг - и находить максимальную величину в каждом Xi Площадь := Сумма всех произведений по i ( deltaX * ВысотаВточкеXi ) Добавлено ну и рисунок Вы выложили! Целое эпическое полотно!! позволю себе продублировать его в своём сообщении (немножко подрезав, разумеется!) Последний раз редактировалось Serge_Bliznykov; 16.04.2011 в 22:45. |
17.04.2011, 06:25 | #3 |
Пользователь
Регистрация: 29.01.2009
Сообщений: 60
|
спасибо конечно за редакцию рисунка) по поводу "в лоб":
то есть найти минимальный шаг? что за максимальная величина в каждом xi? Хотя приглядевшись первый метод показался более понятным, трудность теперь в одном, закодить Последний раз редактировалось sp.caster; 17.04.2011 в 06:56. |
17.04.2011, 11:18 | #4 | |||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Искать его прийдётся действительно по значения координат - прийдётся выделить в каком минимальном десятичном разряде координат есть значимая величина. Кстати, если координаты целочисленные, то шаг можно всегда брать равным единице и не морочиться! Если же координаты вещественные, то шаг должен быть не больше, чем единичка в наименьшем значащем разряде. Ну, если даны координаты вертикальных сторон: 10, 12.5, 22.75, 25.1, 75.578, 100 то, очевидно, что наименьших значимый разряд - это тысячные (координата 75.578) и шаг должен быть 0.001 Кстати, если координаты представлены действительными числами, то можно подойти и с другой стороны. Взять заведомо малый шаг. Тогда, в худшем случае, получится не точное, а приближённое значение площади. но, с другой стороны - использование вещественных (действительных) чисел уже само по себе предполагает возможность отклонений (погрешности). Цитата:
тогда, перебрав в цикле все прямоугольники, у которых координата левой стороны <=X и, одновременное, координата правой стороны >=X мы можем получить все высоты прямоугольников в данной точке. Очевидно, что нас интересует максимальное значение высоты (это будет самый высокий прямоугольник, перекрывающий остальные прямоугольники в данной точке). Вот эту высоту и надо умножать на шаг приращения. Получим площать маленького вертикального прямоугольничка. А вообще, этот способ мне наявело графическим смыслом определённого интеграла (см. например, википедию) Цитата:
Успехов в реализации. |
|||
17.04.2011, 12:49 | #5 |
Пользователь
Регистрация: 29.01.2009
Сообщений: 60
|
Спасибо огромное, а как задать в программе некое случайное количество прямоугольников случайных размеров и в случайном месте? Полагаю начинать мне надо именно с этого)
м-м-м, снимаю вопрос, т.к. предположу что есть входной файл с числом прямоугольников и соответственно координатами левого верхнего и правого нижнего угла прямоугольников Последний раз редактировалось sp.caster; 17.04.2011 в 13:36. |
17.04.2011, 16:59 | #6 |
Пользователь
Регистрация: 29.01.2009
Сообщений: 60
|
как перебирать прямоугольники? что-то блин ничего у меня не получается
|
17.04.2011, 17:49 | #7 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
|
|
17.04.2011, 21:19 | #8 |
Пользователь
Регистрация: 29.01.2009
Сообщений: 60
|
Для меня проблема закодить, а не в понимании... Я представляю вроде как осуществить решение, нужно составить каким-то неведомым для меня образом массив из 3 значений, (x, н (или к), h), где х - координата новой стороны очередного прямоугольника, н и к, начало или конец этой стороны соответственно, а h - высота. Далее, перебирая значения по х и учитывая высоту, суммируем по частям площади прямоугольников. Проблема перевести в код=(
Последний раз редактировалось sp.caster; 18.04.2011 в 14:28. |
18.04.2011, 16:56 | #9 |
Пользователь
Регистрация: 29.01.2009
Сообщений: 60
|
фак, завтра сдавать
|
18.04.2011, 16:59 | #10 | |
Made In USSR!
Старожил
Регистрация: 01.09.2010
Сообщений: 3,657
|
Цитата:
"...В жизни я встречал друзей и врагов.В жизни много всего перевидал.Солнце тело мое жгло, ветер волосы трепал,но я смысла жизни так и не узнал..."
(c) Юрий Клинских aka "Хой" |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Найти площадь фигуры | samouelson | Помощь студентам | 2 | 17.12.2010 20:22 |
как найти ось на жёстком диске | alex(21) | Свободное общение | 10 | 07.10.2010 15:04 |
Найти S – суммарную площадь N равнобедренных треугольников | sllh_111 | Помощь студентам | 7 | 08.05.2010 21:03 |