Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 900 б
- Dwayne_Johnson 870 б
27 июня 2023 16:14
492
Выпуклость многоугольника
Входные данные
В первой строке вводится одно число 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
Остались вопросы?
Еще вопросы по категории Информатика
1 Тренировочная задача 2 [1 балл) Даны Минимальная температура, максимальная температура и текущая температура. Выведи действие климат-контроля: Если...
Требовалось написать программу вычисления факториала числа n (факториал числа n есть произведение всех целых чисел от 1 до n). Программист торопился и...
Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111. НА C++...
Зарплата менеджера становить 200$ + відсоток від продажу: продаж до 500$ – 3%, 500 –1000$ – 5%, понад 1000$ – 8%. Користувач вводить з клавіатури ріве...
Все формулы на нахождение задач по информатике 8-9 класс...