Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.03.2010, 14:11
Максим1990

 
Сообщений: n/a

выделение максимальной площади
В прямоугольнике (макс. 30 000 Х 30 000) заданы координаты точек (макс. 10 000 точек). Найти прямоугольник внутри, чтобы его стороны были параллельны осям координат, внутри него не было точек (на границе могут) и площадь была максимально возможной.
Есть идеи? Работать должно быстро (секунду-две на макс. параметрах).
  #2  
Старый 28.03.2010, 19:22
гость

 
Сообщений: n/a

Приводите ссылку.

O(n^2 log n) устроит?
  #3  
Старый 29.03.2010, 13:07
Максим1990

 
Сообщений: n/a

Думаю, должно пройти. Ссылку на что?
  #4  
Старый 29.03.2010, 13:25
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

существуют алгоритмы, позволяющие за O(M log^3(M)) и O(M log^2(M)) найти решение, где M - количество точек, т.е. для слабого заполнения это выгоднее, чем O(N^2), где N - размер поля.

http://portal.acm.org/citation.cfm?i...TOKEN=96618019
правда, нужна подписка acm, но, вероятно, можно попробовать поискать статьи и за бесплатно ...
  #5  
Старый 29.03.2010, 15:16
Максим1990

 
Сообщений: n/a

Спасибо за ссылку, но не могу разобраться как от туда скачать. Это платный ресурс?
  #6  
Старый 29.03.2010, 15:40
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Это платный ресурс?
Ну да. Как я понимаю, оплачивается подписка, и появляется доступ к статьям ACM
  #7  
Старый 29.03.2010, 15:49
Максим1990

 
Сообщений: n/a

Хм, $15.00 за статью - для меня многовато
  #8  
Старый 29.03.2010, 16:01
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

ну раз алгоритмы существуют и фамилии авторов известны, надо искать, где-то могут встретиться или сам статьи, или хотя бы идеи.
  #9  
Старый 29.03.2010, 17:16
гость

 
Сообщений: n/a

ссылку на задачу приводи где ты ее нашел. а то вдруг это с какого-то текущего контеста а ты просто читер (уже были тут инциденты).
  #10  
Старый 29.03.2010, 22:29
Максим1990

 
Сообщений: n/a

Задача - моя лабораторная по теории алгоритмов (2й курс). Все задачи и т.д. лежат на сервере http://acm-test.bsu.by/index.jsp (войти не сможете, у каждого студента свой аккаунт).
Если не убедительно - могу на мыло кинуть скриншоты.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Агоритм выделение суммы полных квадратов Jim Математические алгоритмы 4 19.10.2009 00:09
Нахождение фигуры максимальной площади alienlab Вычислительная геометрия 1 28.04.2009 20:14
поиск цикла максимальной длинны в графе гость Графы 2 21.12.2008 04:00
Нахождение прямоугольника максимальной площади гость Задачи 13 15.05.2008 20:49
выделение геометрических фигур Ира Вычислительная геометрия 1 13.11.2006 00:08