Mow

Nick is in charge of managing a lawn which can be represented as a convex polygon.

Since he didn’t manage the lawn for a long time, the grass has grown up too long and he doesn’t like it. So, he decided to mow the grass in the lawn.

He can either mow the grass by hand or hire a mowing machine.

Mowing by hand costs A euro(s) per unit area and hiring a mowing machine costs B euro(s) per unit area. Unfortunately, the circle-shaped mowing machine must not get out of his lawn while mowing, that is, any point of the machine must be strictly inside the lawn or on the border. The machine cuts all the grass in its circle.

Any grass is considered to be cut only once even though the machine passed over it several times.

Find out the minimal amount of money he needs for mowing his lawn.

The first line contains an integer T (1≤T≤100), denoting the number of test cases.

The first line of each test case contains two integers n (≤200) and r (0<r≤10000), which is radius of the machine.

The next line contains two integers A and B (0≤A,B≤1000).

Following n lines contain two integers $x_i$ and $y_i$ (|$x_i$ |,|$y_i$ |≤10000), coordinates of points representing his lawn in order of traversal.

It is guaranteed that r is not equal to the radius of inscribed circle.

Output a single line containing the minimal amount of money you need.

Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$).

1
4 1
1 0
0 0
4 0
4 4
0 4

0.858407346410

2020 Multi-University Training Contest 1