основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
baltazar
новичок


Рег.: 09/12/05
Сообщений: 6
Из: Пермь
SNNS4 Problem C "Fences"
      #11890 - 08/22/06 11:23 PM

Суть задачи в следущем: дано n<=150 точек с целочисленными координатами, надо построить два выпуклых полигона, которые покрывают мн-во точек. При этом надо минимизировать суммарную пощадь полигонов, полигоны не могут перекрываться.
Я знаю алгоритм за n^2*(вып. об.), но он даёт TLE.
Может кто-нибудь предложить более быстрый алгоритм?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
EfremovAleksei
здесь был не раз


Рег.: 03/05/06
Сообщений: 36
Re: SNNS4 Problem C "Fences" [Re: baltazar]
      #11892 - 08/23/06 12:44 AM

Это не проходит? (N^2/2)*(Грэхэм N*logN).
А это откуда задача?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
baltazar
новичок


Рег.: 09/12/05
Сообщений: 6
Из: Пермь
Re: SNNS4 Problem C "Fences" [Re: EfremovAleksei]
      #11894 - 08/23/06 04:51 AM

Да, собственно этот алгоритм я реализовал. Задача эта была на 4 этапе SnarkNews Summer Series, но первоисточник - MIT Programming Contest Individual Round Problems 2003,
28 september.

Редактировал baltazar (08/23/06 04:55 AM)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
baltazar
новичок


Рег.: 09/12/05
Сообщений: 6
Из: Пермь
Re: SNNS4 Problem C "Fences" [Re: baltazar]
      #11895 - 08/23/06 04:54 AM

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

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: SNNS4 Problem C "Fences" [Re: baltazar]
      #11900 - 08/23/06 12:21 PM

Итак, во первых довольно странно пытаться строить 2^N ибо там будут миллионы невозможных вариантов.
Основная идея - разделить вершины на 2 множества и построить к нему оболочки по отдельности.
Проще всего это сделать так: перебрать две точки, задающие прямую и пихать точки которые "слева" в одно множество, а "справа" в другое. При этом нужно будет перебрать оба варианта расположения этих двух точек.
Получаем N^2 действий по N.
Далее строим выпуклые оболочки (Грэхэмом за NlogN).
Получаем хороший алгоритм за О(N^3*logN).
Но он получает ТЛ.
Пропатчить его до O(N^3) можно довольно просто: заметим что N<=150, поэтому давайте пользоваться квадратной памятью. Можно зарание отсортировать по углу от каждой вершины(как при построении выпуклой оболочки) и запомнить эти данные в квадратном массиве.
Далее выполняется то же что и при решении за куб логн но когда мы строим оболочку для множества мы не будем сортировать, а найдём самую нижнюю( правую ) точку и загрузим из массива всё уже отсортированное а далее, как обычно, проход грэхэма и готовая оболочка. Можно еще немного ускориться не отсортировав всё сначала, а сортируя по мере надобности( просто "самых нижних-правых" точек не слищком много) и запоминая.
Это решение не должно ТЛиться по идее( сам еще сабмитить не пробовал ).
З.Ы. А три точки на одной прямой лежат для того чтобы нам можно было бы не париться при сортировки и искать самую удалённую точку с данным углом.
З.Ы. Эти контесты называются SNSS, а не SNNS.

Надеюсь поможет...

Редактировал _МГ_ (08/23/06 12:23 PM)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
baltazar
новичок


Рег.: 09/12/05
Сообщений: 6
Из: Пермь
Re: SNNS4 Problem C "Fences" [Re: _МГ_]
      #11918 - 08/24/06 03:23 AM

Да, спасибо, идея хорошая. Но я уже с помощью n^3logn смог акцептнуть задачку.
Суть была в следующем: после того как я разделил множество точек прямой на две части, мне необходимо было решить судьбу оставшихся 2х точек на прямой. Я перебирал всё варианты и для каждого строил ВО отдельно. Потом я понял, что можно построить отдельно сначала выпуклые оболочки для точек которые лежать строго над прямой, и под прямой. А потом уже, когда я захочу туда добавить точку на прямой, я смогу это сделать за о(эн). в результате число вызовов прохода Грэхэма уменьшилось и прога зашла.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: SNNS4 Problem C "Fences" [Re: baltazar]
      #11922 - 08/24/06 09:40 AM

Ну у меня тоже такая мысль была, но только добавление работает в худшем случае(все на оболочке) ровно столько же сколько и грэхэм. (Или ты просто от сортировки избавился?)

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
baltazar
новичок


Рег.: 09/12/05
Сообщений: 6
Из: Пермь
Re: SNNS4 Problem C "Fences" [Re: _МГ_]
      #11929 - 08/24/06 09:25 PM

Если у нас есть выпуклая оболочка, заданная обходом по часовой стрелке, то можно добавить в неё току за О(эн). Зачем сортировать-то?

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: SNNS4 Problem C "Fences" [Re: baltazar]
      #11932 - 08/24/06 11:06 PM

Да. И в худшем случае это будет работатть столько же сколько и грэхэм( никакой сортировки ).

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 400 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 15325

Rate this topic

Переход в