Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 11.10.2008, 14:15   #1
StakanpORTvejna
Пользователь
 
Регистрация: 31.08.2007
Сообщений: 37
По умолчанию помогите с задачей

Дано N точек (N>2) с целочислеными координатами,некторые из них являються вершинами выпуклого многоугольника,а остольные находяться внутри его.Любые три точки не лежат на одной прямой.Определить число и номера вершин многоугольника..Ограничения:число точек не более 20.Модули координат не превосходят 30000.
Например:
Ввод:
7 - число точек
0 7 координаты точек
0 3
1 3
2 2
3 0
3 5
5 0
Вывод
5 - число вершин
1 2 5 6 7 - номера вершин..

Паскаль знаю более-менее...подскажите хотябы с чего начять,потому что мыслей нету
StakanpORTvejna вне форума Ответить с цитированием
Старый 11.10.2008, 18:19   #2
alexBlack
Участник клуба
 
Регистрация: 12.10.2007
Сообщений: 1,204
По умолчанию

Прежде всего для отрезка a(x1, y1) b(x2, y2) определитель

| x1 y1 1 |
| x2 y2 1 |
| x3 y3 1 |

будет иметь один знак для всех точек (x3, y3), лежащих по одну сторону от прямой и другой знак для точек, лежащих по другую сторону.

Можно начать с самой нижней точки (любой из них). Эта точка будет текущей. Для нее перебираем все оставшиеся точки (кроме уже выбранных) и для этого отрезка вычисляем определители со всеми остальными точками. Если все знаки совпадают, точка является очередной вершиной многоугольника. Она становится текущей. Цикл завершаестя, когда на очередном этапе будет найдена самая первая выбранная точка.
alexBlack вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с задачей drossel Общие вопросы C/C++ 9 01.06.2008 20:45
Помогите с задачей Лёха Паскаль, Turbo Pascal, PascalABC.NET 7 08.02.2008 20:08
Помогите с задачей bel_ka Общие вопросы C/C++ 13 26.12.2007 19:23
Помогите с задачей на С++ zub Общие вопросы C/C++ 1 06.12.2007 19:27


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS
Здесь нужно купить рекламу за 7 тыс руб в месяц! )
пишите сюда - alarforum@yandex.ru
ИКС 840