Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 900 б
- Dwayne_Johnson 870 б
27 июня 2023 16:14
465
Выпуклость многоугольника
Входные данные
В первой строке вводится одно число 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
Остались вопросы?
Еще вопросы по категории Информатика
Напишите следующие числа в естественной форме а) 0,3800456 умножить на 10 во второй степени б) 0,245 умножить на 10 в минус третьей степени в) 1,25690...
Информатика 7 класс.Как решать данные задачи,объясните пожалуйста)...
Для групповых операций с файлами используются маски имен файлов. Определите, какой из указанных имен файлов удовлетворяет маске: ?*?.срр Символ «?» о...
ПОМОГИТЕ ПОЖАЛУЙСТА!!!!!...
2. Сравните (поставьте знак отношения): 3 байтах 24 бита 1 Кбайт + 9000 бит 1536 бит + 1,5 Кбайт 1536 бит + 1,5 Кбайт 8192 байта + 9 Кбайт 100 Кбайт +...