Polygons. Convex hulls


Plus
Pin


Problem description Progress
ID 33698. convex hull
Темы: Polygons. Convex hulls   

N points are given on the plane. You need to construct a convex hull of a given set of points. Print two numbers: perimeter and area.

Input
The first line contains the number of points N, 1≤N≤10000. Each of the following N lines contains two integers – xi and yi coordinates. All modulo numbers do not exceed 104.

Imprint
Output two numbers: the perimeter and the area of ​​the convex hull.
 

Input Output
4
0 0
34
3 1
60
16.0000000000
12.0000000000

ID 38674. Convex polygon
Темы: Polygons. Convex hulls   

Input
The first line contains one number N (3≤N≤100000). Next, N lines contain a pair of numbers – coordinates of the next vertex of a simple polygon in clockwise or counterclockwise order.

Imprint
Print one line: “YES”, if the given polygon is convex, and “NO” otherwise.

Examples
# Input Output
1 3
0 0
0 1
10
YES
2 6
0 0
0 2
1 2
1 1
2 1
20
NO

ID 38675. Does the point lie inside the polygon
Темы: Polygons. Convex hulls   

Input
The first line contains three integers – N (3≤N≤100000) and point coordinates. Next, N lines contain a pair of integers – coordinates of the next vertex of a simple polygon in clockwise or counterclockwise order.

Imprint
Print  one line: “YES”, if the given point is contained in the reduced polygon or on its boundary, and “NO” otherwise.
 

Examples
# Input Output
1 3 2 3
1 1 
10 2
28
YES

ID 38676. convex hull
Темы: Polygons. Convex hulls   

N points are given on the plane. You need to construct a convex hull of a given set of points. Print two numbers: perimeter and area.

Input
The first line contains the number of points N, 1≤N≤10000. Each of the following N lines contains two integers – xi and yi coordinates. All modulo numbers do not exceed 104.

Imprint
Output two numbers: the perimeter and the area of ​​the convex hull.
 

Examples
# Input Output
1 4
0 0
34
3 1
60
16.0000000000
12.0000000000