Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Как сократить полный перебор!

Автор: sofware 30.11.2006, 19:41

Дано N прямоугольников, стороны которых паралельны осям координат. Найти площадь, которую занимают эти прямоугольники. Входящие данные(файл Priam.in): В первой строке находится N(N<=3000). Далее в следующих N строках находятся координаты левого верхнего и правого нижнего угла каждого прямоугольника(координаты - целые числа в пределах от 0 до 1000000). Исходящие данные(файл Priam.out): В исходящий файл записать одно число - площадь покрытую прямоугольниками. Результат записать с тремя знаками после запятой. Пример: Priam.in 3 1 2 3 1 2 2 3 1 2 4 3 2 Priam.out 5.000

Автор: sofware 30.11.2006, 21:55

Важно:N<=3000

Автор: anwe 30.11.2006, 22:12

Так, а в чем вопрос-то?

Автор: sofware 30.11.2006, 22:25

Подскажите алгоритм, уже долго мозги сушу, никак немогу придумать сам, вот и обратился за Help-ом

Автор: Zero 30.11.2006, 22:59

Ну первое что приходит в голову, это так: 1. Создаёш двуменрый массив, размером координатной плоскости, заполненый нулями по умолчанию; 2. а дальше, при вводе каждого прямоугольника, границии пересечения заполняются единицами; 3. и в конце количество единиц будет пропорцианально площади.

Автор: sofware 30.11.2006, 23:16

Да но как описать масив [1..1000000,1..1000000]

Автор: maxim1000 30.11.2006, 23:44

нет, это кощунство делать массив в подобной задаче, пропорциональным размеру поля можно сделать, например, так: делаем список (или массив), добавляем по одному прямоугольники при добавлении каждого прямоугольника проверяем его пересечения с теми, которые уже в списке если пересечений нет, просто добавляем, если есть, разбиваем добавляемый прямоугольник на части, которые либо полностью лежат в рассматриваемом пересечении, либо вне его, те, которые внутри игнорируем, те, которые снаружи добавляем (с проверкой на пересечения с другими прямоугольниками в списке) части, наверное, удобнее будет брать прямоугольные тогда при разбиении прямоугольника будет получаться от 2 до 4 частей в конце концов получится список из непересекающихся прямоугольников, площадь которых можно посчитать простой суммой

Автор: Zero 30.11.2006, 23:50

Цитата(sofware @  1.12.2006,  00:16 ) Да но как описать масив [1..1000000,1..1000000] Статический никак. Можно использовать динамический, но это плохой вариант. Кроме того, если смысл задания заключается в написании лабораторки или т.п. то размер не имеет значения, т.е. можно взять и меньше. Но если оно задано, жёстко, то либо динам. массив, либо менять алгоритм. Если бы я делал, то я бы сделал так: 1. создал бы одномерный динамический массив из 2-ух элементов который содержал бы координаты итоговой площади; 2. условно принято, что пока площадь пуста; 3. дальше цикл по каждому прямоугольнику, каждый раз добавляя информацию о новой площади в этот массив, изменяя его каждый раз. 4. в итоге будут координаты полной площади. Добавлено @ 23:53  Опоздал. Но принцип такойже. Добавлено @ 23:53  PS: в начале я давал с учётом на новичка.

Автор: sofware 30.11.2006, 23:58

Проблема: я неумею работать с динамикой!!!Что же мне делать??

Автор: Zero 1.12.2006, 00:51

Используй статический массив на 100 элементов например или больше, а дальше введи число N например, которое будет показывать количество актуальных элементов.

Автор: sofware 1.12.2006, 08:19

Всю ночь мучился, ничего не получается, помогите пожалуйста с реализацией

Автор: Zero 1.12.2006, 09:33

sofware, тут решаются отдельные вопросы, а не реализация полностью. Если у тебя неполучается только какя-то часть кода, то её и нужно приводить, а не задание целиком.

Автор: sofware 1.12.2006, 20:34

Ну и на этом спасибо  А где делают полностью???

Автор: Zero 2.12.2006, 00:46

Цитата(sofware @  1.12.2006,  21:34 ) А где делают полностью??? Полностью делают в разделе ЦентрПомощи...   Если ты был бы повнимательнее, то прочитал бы правила вверх, прям написаны. Цитата Описывая свою проблему, не забывайте указывать компилятор и версию. Студентам! Здесь помогают в решении проблем, а не делают работу за вас! Если Вам нужно сделать работу, обращайтесь в Центр помощи Не просите ответить вам на e-mail, ICQ и т.п. Все ответы помещаются только здесь. Но там есть один недостаток: шанс получить там ответ гараздо ниже чем тут. Но тут в свою очередь чтобы получить ответ (в 90% случаев) нужно самому что-либо изучать.

Автор: maxim1000 2.12.2006, 01:57

есть ещё раздел "Работа", но там за деньги

Автор: sofware 2.12.2006, 09:42

Спасибо

Автор: Grasshopper 2.12.2006, 13:16

Цитата(Zero @  1.12.2006,  05:51 ) Используй статический массив на 100 элементов например или больше, а дальше введи число N например, которое будет показывать количество актуальных элементов.  При такой реализации несколько проблем: 1) Под все переменные в Паскале отведено 64к. А если N<=3000 то этого ну никак не хватит. Значит подразумевается, что это можно как-то сделать без массива. 2) Время работы программы при полном переборе... внушает) 1500 циклов в худшем случае)

Автор: Zero 2.12.2006, 13:56

Цитата(Grasshopper @  2.12.2006,  14:16 ) При такой реализации несколько проблем: В учебных целях такие реализации делают очень часто. Цитата(Grasshopper @  2.12.2006,  14:16 ) 1) Под все переменные в Паскале отведено 64к. И что с того, а одна переменна типа integer занимает всего два байта. Этого в полне достаточно, чтобы описать очень большое количество координатных точек. Цитата(Grasshopper @  2.12.2006,  14:16 ) А если N<=3000 то этого ну никак не хватит. Значит подразумевается, что это можно как-то сделать без массива. Говоришь если меньше,    Если N>3000 например N=99999999999999999, тогда хватит?       PS: ты сначала вдумайся чё написал, потом нажимай кнопку отправить.   Цитата(Grasshopper @  2.12.2006,  14:16 ) 2) Время работы программы при полном переборе... внушает) 1500 циклов в худшем случае) Про какие переборы ты говоришь. Ты сначала дочитай 2-ой пост с алгоритмом до конца потом говори. Про перебор это я в начале написал как простейший случай, но в данном он не подходит... и это тоже я уже описал.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)