Модераторы: volvo877, Snowy, MetalFan

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Как сократить полный перебор! 
V
    Опции темы
sofware
  Дата 30.11.2006, 19:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



 smile 
Дано 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:56
PM MAIL   Вверх
sofware
Дата 30.11.2006, 21:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



 smile Важно:N<=3000
PM MAIL   Вверх
anwe
Дата 30.11.2006, 22:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 748
Регистрация: 2.9.2006

Репутация: нет
Всего: 23



Так, а в чем вопрос-то?
PM MAIL   Вверх
sofware
Дата 30.11.2006, 22:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



Подскажите алгоритм, уже долго мозги сушу, никак немогу придумать сам, вот и обратился за Help-ом smile 
PM MAIL   Вверх
Zero
Дата 30.11.2006, 22:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24



Ну первое что приходит в голову, это так:
1. Создаёш двуменрый массив, размером координатной плоскости, заполненый нулями по умолчанию;
2. а дальше, при вводе каждого прямоугольника, границии пересечения заполняются единицами;
3. и в конце количество единиц будет пропорцианально площади.
PM MAIL ICQ   Вверх
sofware
Дата 30.11.2006, 23:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



Да но как описать масив [1..1000000,1..1000000] smile 
PM MAIL   Вверх
maxim1000
Дата 30.11.2006, 23:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: нет
Всего: 110



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

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

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


--------------------
qqq
PM WWW   Вверх
Zero
Дата 30.11.2006, 23:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24



Цитата(sofware @  1.12.2006,  00:16 Найти цитируемый пост)
Да но как описать масив [1..1000000,1..1000000]

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

Добавлено @ 23:53 
Опоздал. Но принцип такойже.

Добавлено @ 23:53 
PS: в начале я давал с учётом на новичка.
PM MAIL ICQ   Вверх
sofware
Дата 30.11.2006, 23:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



Проблема: я неумею работать с динамикой!!!Что же мне делать?? smile 
PM MAIL   Вверх
Zero
Дата 1.12.2006, 00:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24



Используй статический массив на 100 элементов например или больше, а дальше введи число N например, которое будет показывать количество актуальных элементов.
PM MAIL ICQ   Вверх
sofware
Дата 1.12.2006, 08:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



Всю ночь мучился, ничего не получается, помогите пожалуйста с реализацией  smile 
PM MAIL   Вверх
Zero
Дата 1.12.2006, 09:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24



sofware, тут решаются отдельные вопросы, а не реализация полностью.
Если у тебя неполучается только какя-то часть кода, то её и нужно приводить, а не задание целиком.
PM MAIL ICQ   Вверх
sofware
Дата 1.12.2006, 20:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 20
Регистрация: 30.11.2006

Репутация: нет
Всего: 1



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

Это сообщение отредактировал(а) sofware - 1.12.2006, 20:41
PM MAIL   Вверх
Zero
Дата 2.12.2006, 00:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24



Цитата(sofware @  1.12.2006,  21:34 Найти цитируемый пост)
А где делают полностью???

Полностью делают в разделе ЦентрПомощи... smile 
Если ты был бы повнимательнее, то прочитал бы правила вверх, прям написаны.
Цитата
Описывая свою проблему, не забывайте указывать компилятор и версию.
Студентам! Здесь помогают в решении проблем, а не делают работу за вас!
Если Вам нужно сделать работу, обращайтесь в Центр помощи
Не просите ответить вам на e-mail, ICQ и т.п. Все ответы помещаются только здесь.


Но там есть один недостаток: шанс получить там ответ гараздо ниже чем тут. Но тут в свою очередь чтобы получить ответ (в 90% случаев) нужно самому что-либо изучать. smile 
PM MAIL ICQ   Вверх
maxim1000
Дата 2.12.2006, 01:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: нет
Всего: 110



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


--------------------
qqq
PM WWW   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi"
THandle
Rrader
volvo877

Запрещается!

1. Обсуждать и делится взломанными компонентами или программным обеспечением

2. Публиковать ссылки на варез

3. Оффтопить

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, THandle, Rrader, volvo877.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Object Pascal: кроссплатформенные технологии | Следующая тема »


 




[ Время генерации скрипта: 0.0820 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.