Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 895 б
- Dwayne_Johnson 865 б
27 июня 2023 16:14
316
Выпуклость многоугольника
Входные данные
В первой строке вводится одно число 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
Остались вопросы?
Еще вопросы по категории Информатика
Запишите раздел описания переменных,необходимых для вычисления: а) значения функции y=x^2 б) площади прямоугольника в) стоимости покупки, состоящей...
!!!...
На вашем смартфоне установлено настолько много мобильных приложений, что их иконки уже не умещаются на одном экране. Поэтому вы часто не можете быстро...
Видеопамять предназначена для: а) хранения информации о количестве пикселей на экране монитора б) хранения информации о цвете каждого пикселя экрана...
Перевести число 2048 кб в Мб...