Лучшие помощники
- Megamozg 2200 б
- Matalya1 1800 б
- DevAdmin 1705 б
- arkasha_bortnikov 895 б
- Dwayne_Johnson 860 б
27 июня 2023 16:14
280
Выпуклость многоугольника
Входные данные
В первой строке вводится одно число N (3≤N≤100000). Далее в N строках задается по паре чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Выходные данные
Выведите одну строку: “YES”, если приведённый многоугольник является выпуклым, и “NO” в противном случае.
1
ответ
Решение:
Для проверки выпуклости многоугольника нужно проверить, что все углы многоугольника меньше 180 градусов. Для этого можно использовать векторное произведение.
Пусть у нас есть три последовательные вершины многоугольника A, B и C. Тогда векторное произведение векторов AB и BC будет равно:
AB x BC = (xB-xA)*(yC-yB) - (yB-yA)*(xC-xB)
Если знак этого выражения положительный, то угол ABC острый, если отрицательный, то тупой. Если выражение равно 0, то точки лежат на одной прямой.
Таким образом, для каждой тройки последовательных вершин нужно вычислить векторное произведение и проверить его знак. Если хотя бы одно из произведений отрицательное, то многоугольник не выпуклый.
Пример решения на Python:
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
def cross_product(a, b, c):
return (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0])
is_convex = True
for i in range(n):
cp = cross_product(points[i-2], points[i-1], points[i])
if cp < 0:
is_convex = False
break
if is_convex:
print("YES")
else:
print("NO")
Для проверки выпуклости многоугольника нужно проверить, что все углы многоугольника меньше 180 градусов. Для этого можно использовать векторное произведение.
Пусть у нас есть три последовательные вершины многоугольника A, B и C. Тогда векторное произведение векторов AB и BC будет равно:
AB x BC = (xB-xA)*(yC-yB) - (yB-yA)*(xC-xB)
Если знак этого выражения положительный, то угол ABC острый, если отрицательный, то тупой. Если выражение равно 0, то точки лежат на одной прямой.
Таким образом, для каждой тройки последовательных вершин нужно вычислить векторное произведение и проверить его знак. Если хотя бы одно из произведений отрицательное, то многоугольник не выпуклый.
Пример решения на Python:
n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]
def cross_product(a, b, c):
return (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0])
is_convex = True
for i in range(n):
cp = cross_product(points[i-2], points[i-1], points[i])
if cp < 0:
is_convex = False
break
if is_convex:
print("YES")
else:
print("NO")
0
·
Хороший ответ
27 июня 2023 16:15
Остались вопросы?
Еще вопросы по категории Информатика
ПОМОГИТЕ...
ЛАБОРАТОРНАЯ РАБОТА № 11
Создание отчета
1. Закладка Отчеты, Создать, Мастер отчетов.(Правонарушители)
- 1 окно выбираем поля (Код правон...
ФУНКЦИЯ. ПОМОГИТЕ С ИНФОРМАТИКОЙ, ПОЖАЛУЙСТА!!...
Составить программу сколько воскресений в 2022 году ...
Что такое деловая графика?Какой вид имеет условная функция ? Как она выполняется ?...
Все предметы