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


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


Условие задачи Прогресс
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