Frontier#4118

Frontier

2 sekundi
16 megabajtov
Lahko

Lilliputian frontier is a convex polygon with non-zero area. The vertices of this polygon are guard towers, which are connected by straight lines. This frontier is too long and expensive for Lilliputia to maintain; therefore, the Lilliputian government has decided to revise it to make it shorter. However, they do not want to build new guard towers, but to use the existing ones as a part of a new frontier.

Each day, frontier guards inspect the frontier. They go from one guard tower to the next, traversing the frontier in a clockwise direction. Guard towers are numbered from to according to this inspection order. The frontier revision should not change this way of inspection, and the area of Lilliputia must remain non-zero.

For example, the frontier in the picture (axes are in kilometers) is traversed along the ----- route, which is kilometers long. To make the frontier as short as possible, Lilliputia should revise it so that the route becomes ---, thus reducing its length to kilometers.

However, Lilliputia has several historical monuments, which are a matter of national pride. The historical monuments must remain inside Lilliputia at any cost and must not end up on the frontier. The task is to design the shortest possible frontier that keeps all the historical monuments inside Lilliputia.

In the picture, two historical monuments are marked "A" and "B". To keep them inside Lilliputia, the shortest possible frontier will have the traversal path ---- with a length of kilometers.

Vhod

The first line of the input contains two integers and , separated by a space. (3 \le N \le 50) is the total number of guard towers on the Lilliputian frontier, and (0 \le M \le 1000) is the total number of historical monuments inside Lilliputia.

Next lines contain the coordinates of the guard towers listed in clockwise order, followed by lines with the coordinates of the historical monuments. All coordinates are given as two integers ( and ), separated by a space. Coordinates are measured in kilometers, and each coordinate does not exceed by absolute value. All guard towers are at distinct points.

Izhod

Print a single real number: the minimal possible length of the Lilliputian frontier (in kilometers), accurate to two digits after the decimal point.

Primeri

Primer 1

Loading
Loading