402383: GYM100741 E Slicing cheese

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Slicing cheesetime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

You have a polygon defined by N points (xi, yi) and a polyline defined by M points (aj, bj). Polyline cuts polygon into some number of smaller polygons. Find the total perimeter P of resulting polygons. Polyline is guaranteed to start and end outside of the polygon. Each segment of polyline has no more than 1 common point with any segment of polygon segments. All points in the input are distinct. (aj, bj) does not lie on any line segment of the polygon.

Input

First line contains integers N and M. (3 ≤ N ≤ 1000, 2 ≤ M ≤ 1000)

Next N lines contain integers xi and yi.

Next M lines contain integers aj and bj.

( - 105 ≤ xi, yi, aj, bj ≤ 105)

Output

Output a single number P.

The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6.

ExamplesInput
4 2
0 0
10 0
10 10
0 10
5 -1
5 11
Output
60.000000000000000

加入题单

上一题 下一题 算法标签: