Форум программистов, компьютерный форум CyberForum.ru

Очень стремная задача - C++

Восстановить пароль Регистрация
 
K1m
 Аватар для K1m
9 / 9 / 1
Регистрация: 02.01.2012
Сообщений: 167
08.04.2012, 13:53     Очень стремная задача #1
На плоскости задано N точек, которые пронумерованы слева на право (а при равных абсциссах снизу вверх). Нужно создать программу, которая строит многоугольник, который является выпуклой их оболочкой, не более чем за C*N действий.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2012, 15:12     Очень стремная задача #2
Цитата Сообщение от K1m Посмотреть сообщение
На плоскости задано N точек, которые пронумерованы слева на право (а при равных абсциссах снизу вверх). Нужно создать программу, которая строит многоугольник, который является выпуклой их оболочкой, не более чем за C*N действий.
стрёмно, мда.
алгоритмы какие-нибудь гуглил?
пробовал искать, что-нибудь вроде
find convex containing set of points
Скажи алгоритм тебе помогут.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
08.04.2012, 15:13     Очень стремная задача #3
Алгоритм Грэхема-Эндрю
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2012, 15:18     Очень стремная задача #4
Цитата Сообщение от Nekto Посмотреть сообщение
Алгоритм Грэхема-Эндрю
Это конечно близко к линейному, но всё равно O (N log N)
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
08.04.2012, 15:59     Очень стремная задача #5
http://e-maxx.ru/algo/convex_hull_graham

как видите оно работает
Миниатюры
Очень стремная задача  
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
08.04.2012, 16:01     Очень стремная задача #6
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Это конечно близко к линейному, но всё равно O (N log N)
тогда Алгоритм Джарвиса
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.04.2012, 20:15     Очень стремная задача
Еще ссылки по теме:

C++ очень сложная задача
C++ Странная ошибка при компиляции очень очень большой проги ,,boomerang,,

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
K1m
 Аватар для K1m
9 / 9 / 1
Регистрация: 02.01.2012
Сообщений: 167
09.04.2012, 20:15  [ТС]     Очень стремная задача #7
Спасибо, народ. Сейчас буду реализовывать.
Yandex
Объявления
09.04.2012, 20:15     Очень стремная задача
Ответ Создать тему
Опции темы

Текущее время: 03:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru