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

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

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

Дано 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
Репутация: 920
По умолчанию

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

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

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


22:36.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.