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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Kolbusdkiy
 Аватар для Kolbusdkiy
0 / 0 / 0
Регистрация: 14.10.2013
Сообщений: 112
#1

Определить, является ли заданный многоугольник выпуклым - C++

10.04.2014, 14:40. Просмотров 584. Ответов 3
Метки нет (Все метки)

Помогите решить.
Определить, является ли заданный многоугольник выпуклым. В первой строке одно число - N . Далее в N строках по паре чисел - координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2014, 14:40     Определить, является ли заданный многоугольник выпуклым
Посмотрите здесь:

Выяснить, является ли заданный символ цифрой C++
Ввести количество точек, получить многоугольник, закрасить многоугольник построчно. C++
C++ Определить является ли заданный четырехугольник трапецией
C++ Определить выпуклый ли многоугольник.
Выяснить, является ли заданный текст идентификатором C++
C++ Является ли четырехугольник, заданный координатами вершин, прямоугольником
C++ Определить, является ли заданный текст записью числа в шестнадцатиричной системе счисления
Определить является ли пятиугольник выпуклым и можно ли около него описать окружность C++
Определить, является ли заданный текст двоичной записью числа, кратного 6 C++
Строка: Проверить, является ли заданный символ буквой, числом или специальным символом? C++
Определить, является ли заданный массив пилообразным C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TenGen
Будущее рядом
 Аватар для TenGen
97 / 95 / 20
Регистрация: 06.03.2014
Сообщений: 342
10.04.2014, 15:23     Определить, является ли заданный многоугольник выпуклым #2
Kolbusdkiy, предложу такой вариант: программа находит координаты каждой точки, затем вычисляет для каждой точки угол (который мы можем найти с помощью треугольника, построенного из самой точки и двух соседних). Не уверен в решении, с математикой не очень хорошие отношения.
fishec
 Аватар для fishec
118 / 118 / 30
Регистрация: 07.09.2013
Сообщений: 338
10.04.2014, 16:27     Определить, является ли заданный многоугольник выпуклым #3
Можно пройти по всем ребрам, для каждого ребра берем следующую по часовой стрелке вершину - она должна быть справа от прямой(вектора ребра) для всех ребер.
palva
 Аватар для palva
2439 / 1661 / 208
Регистрация: 08.06.2007
Сообщений: 6,575
Записей в блоге: 4
10.04.2014, 23:04     Определить, является ли заданный многоугольник выпуклым #4
По треугольникам хорошая идея. По трем последовательным вершинам вычисляется площадь треугольника (определитель четвертого порядка). При обходе многоугольника все эти площади должны быть одного знака.

Другой алгоритм. Обходим многоугольник и для каждых двух последовательных вершин A и B составляем уравнение прямой AB и в это уравнение подставляем координаты вершины, которая предшествует вершине A и которая идет после вершины B. Эти подстановки должны дать результат одного знака (точки должны находиться по одну сторону от прямой AB).

Добавлено через 5 часов 51 минуту
Все-таки второй алгоритм надо забраковать. По вычислениям это то же, что и первый алгоритм. Подстановка точки в уравнение прямой и дает площадь треугольника с некоторым положительным коэффициентом. Получается, что площадь каждого треугольника при обходе многоугольника вычисляется дважды. То есть он в два раза медленнее работает.

А в первом алгоритме в формуле площади треугольника есть коэффициент 1/2. Его использовать не нужно, поскольку нам важно узнать лишь знак площади.
Yandex
Объявления
10.04.2014, 23:04     Определить, является ли заданный многоугольник выпуклым
Ответ Создать тему
Опции темы

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