Лучшие помощники
27 июня 2023 16:14
268

Выпуклость многоугольника

Входные данные

В первой строке вводится одно число 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")
0
·
Хороший ответ
27 июня 2023 16:15
Остались вопросы?
Найти нужный