|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.10.2008, 15:15 | #1 |
Пользователь
Регистрация: 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 - номера вершин.. Паскаль знаю более-менее...подскажите хотябы с чего начять,потому что мыслей нету |
11.10.2008, 19:19 | #2 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Прежде всего для отрезка a(x1, y1) b(x2, y2) определитель
| x1 y1 1 | | x2 y2 1 | | x3 y3 1 | будет иметь один знак для всех точек (x3, y3), лежащих по одну сторону от прямой и другой знак для точек, лежащих по другую сторону. Можно начать с самой нижней точки (любой из них). Эта точка будет текущей. Для нее перебираем все оставшиеся точки (кроме уже выбранных) и для этого отрезка вычисляем определители со всеми остальными точками. Если все знаки совпадают, точка является очередной вершиной многоугольника. Она становится текущей. Цикл завершаестя, когда на очередном этапе будет найдена самая первая выбранная точка. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите с задачей | 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 |