Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 900 б
- Dwayne_Johnson 865 б
27 июня 2023 16:14
328
Выпуклость многоугольника
Входные данные
В первой строке вводится одно число 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
Остались вопросы?
Еще вопросы по категории Информатика
30 БАЛЛОВ ТОМУ КТО РЕШИТ!!! !!!Задача на c++ !!! Дана строка. Удалите из нее все символы, чьи индексы делятся на 3....
Получить целое частное можно с помощью операции … mod div / |...
Какая кнопка или кнопки позволит(лят) тебе обновить окно (очистка кэша)? CTRL с любой стрелкой CTRL + C CTRL + V CTRL + Z CTRL + A ALT+ F4...
Представьте десятичные числа в беззнаковом 8-разрядном формате: 65 и 125...
составьте блок-схему алгоритма выполнения домашнего задания по математике, состоящего из нескольких примеров. Оформите блок-схему в графическом редакт...