Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 11.10.2008, 15: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, 19: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 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с задачей drossel Общие вопросы C/C++ 9 01.06.2008 21: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