Многоугольники. Выпуклые оболочки


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 34878. Площадь многоугольника
Темы: Многоугольники. Выпуклые оболочки   

На плоскости задан многоугольник координатами вершин в порядке их обхода. Многоугольник не обязательно выпуклый. Требуется найти его площадь.

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

Сначала вводится число N - количество вершин многоугольника (3<=N<=100), затем N пар вещественных чисел, задающих координаты его вершин.

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

Выведите площадь многоугольника не меньше, чем с 3 знаками после десятичной точки.

Примеры.

входные данные
3
1 1
1 4
7 4
 
выходные данные
 9.00000000000000E+0000
ID 33698. Выпуклая оболочка
Темы: Многоугольники. Выпуклые оболочки   

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты xi и yi. Все числа по модулю не превосходят 104.

Выходные данные
Вывести два числа: периметр и площадь выпуклой оболочки.
 

Ввод Вывод
4
0 0
3 4
3 1
6 0		 16.0000000000
12.0000000000

ID 38674. Выпуклость многоугольника
Темы: Многоугольники. Выпуклые оболочки   

Входные данные
В первой строке вводится одно число N (3≤N≤100000). Далее в N строках задается по паре чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные
Выведите одну строку: “YES”, если приведённый многоугольник является выпуклым, и “NO” в противном случае.

Примеры
№ Входные данные Выходные данные
1 3
0 0
0 1
1 0		 YES
2 6
0 0
0 2
1 2
1 1
2 1
2 0		 NO

ID 38675. Лежит ли точка внутри многоугольника
Темы: Многоугольники. Выпуклые оболочки   

Входные данные
В первой строке вводятся три целых числа – N (3≤N≤100000) и координаты точки. Далее в N строках задается по паре целых чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные
Выведите  одну строку: “YES”, если заданная точка содержится в приведённом многоугольнике или на его границе, и “NO” в противном случае.
 

Примеры
№ Входные данные Выходные данные
1 3 2 3
1 1 
10 2
2 8		 YES

ID 38676. Выпуклая оболочка
Темы: Многоугольники. Выпуклые оболочки   

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты xi и yi. Все числа по модулю не превосходят 104.

Выходные данные
Вывести два числа: периметр и площадь выпуклой оболочки.
 

Примеры
№ Входные данные Выходные данные
1 4
0 0
3 4
3 1
6 0		 16.0000000000
12.0000000000

ID 42495. Точка пересечения медиан
Темы: Вычислительная геометрия    Элементарная геометрия    Многоугольники. Выпуклые оболочки   

Точка пересечения медиан

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа X, Y, задающие координаты точки пересечения медиан в треугольнике, образованном  исходными точками.
Числа в ответе должны быть выданы с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные 
1 1 2 4 3 2
 
2.00000 2.33333
 
2 4 3 2 1 1 
2.00000 2.33333

 
ID 42496. Точка пересечения высот
Темы: Вычислительная геометрия    Элементарная геометрия    Многоугольники. Выпуклые оболочки   

Точка пересечения высот

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа X, Y, задающие координаты точки пересечения высот в треугольнике, образованном  исходными точками.
Числа в ответе должны быть выданы с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные 
1 1 2 4 3 2
 
3.0 2.0
 
10 0 12 2 14 5
 
 37.0 -18.0

 
ID 42497. Вписанная окружность
Темы: Вычислительная геометрия    Элементарная геометрия    Многоугольники. Выпуклые оболочки   

Вписанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа X, Y, R, задающие координаты центра и радиус окружности, вписанной в треугольник, образованном  исходными точками.
Числа в ответе должны быть выданы с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
2.12132 2.292893 0.65493
 
10 0 12 2 14 5
 
 11.8789  2.099258  0.1557984


 
 
ID 42498. Описанная окружность
Темы: Вычислительная геометрия    Элементарная геометрия    Многоугольники. Выпуклые оболочки   

Описанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите два числа X, Y, R, задающие координаты центра и радиус окружности, описанной в треугольник, образованном  исходными точками.
Числа в ответе должны быть выданы с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
1.50000 2.50000 1.58114
 
10 0 12 2 14 5
 
-0.50000 12.50000 16.32483


 

 
 
ID 42657. ege_06_057_траектория ЗВЕЗДА
Темы: Многоугольники. Выпуклые оболочки   

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси абсцисс, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … КомандаS]

означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм:
Повтори 12 [Вперёд 10 Направо 216]
Определите, из какого количества отрезков будет состоять фигура, заданная данным алгоритмом. Считайте, что точка пересечения двух отрезков разбивает каждый из них на два отрезка.