以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
ICPC 2023–2024, NERC – Northern Eurasia Finals
St. Petersburg, Novosibirsk, Astana, Kutaisi, December 13th, 2023
Problem I. Innovative Washing Machine
Time limit: 3 seconds
Memory limit: 1024 megabytes
You are asked to help a team that participates in “Innovation Workshop” — an event where teams of
students invent and prototype their innovative ideas. One of the teams developed a new innovative washing
machine that significantly reduces the usage of energy needed for laundry.
The innovative idea was to use a convex polygon instead of a circle for the shape of a washing machine
drum. You are given this polygon. A drum is rotating around some fixed point inside the polygon with a
constant speed of 1 turn in 1 second.
Currently, the prototype is built and testing is started. There are s litres of water in the drum. At each
moment of time, water under the influence of gravity occupies a region with area s at the bottom of the
drum.
Vertices of the polygon that are underwater are under pressure. By Pascal’s law, we know that pressure
is proportional to depth. Let’s define by d1, d2, . . . , dk depths of the vertices that are underwater at
some moment of time, k is the number of underwater vertices. Let’s define the pressure imbalance as
the average difference between underwater vertex depth and the maximum underwater vertex depth, i.e. ( )
k∑ k1 max dj −di . Note that the order of di is not important.k
i=1 j=1
7
6
5
d1
8 d2 d5
d4
d3
1
4
3
2
The polygon from the third test case is rotated. Vertices 1, 2, 3, 4, 8 are underwater.
To select the optimal shape of the drum, the team wants to know the expected value of pressure imbalance
for the moment of time selected uniformly from segment [0, 1] (in seconds). Please help the team to
calculate this value.
Input
The first line contains a single integer t (1 ≤t ≤104) — the number of test cases. The next lines contain
descriptions of test cases.
The first line contains two integers n, s (3 ≤n ≤2 · 105, s ≥1) — the number of vertices in the polygon
and the number of litres of water inside the drum. It is guaranteed that s is less than the area of the
polygon.
Each of the next n lines contains two integers xi, yi (|xi|, |yi| ≤108) — coordinates of polygon vertices.
It is guaranteed that the given points form a convex polygon. The area of the polygon is positive and no
two consecutive segments are collinear. The vertices of the polygon are given in counterclockwise order.
Page 11 of 15
ICPC 2023–2024, NERC – Northern Eurasia Finals
St. Petersburg, Novosibirsk, Astana, Kutaisi, December 13th, 2023
The sum of n for all test cases does not exceed 2 · 105.
Output
For each test case, print a single real number — the expected value of pressure imbalance for a random
uniform moment of time.
Your answer will be accepted if its absolute or relative error does not exceed 10−5; formally, if p is your
|p−j|answer, and j is the jury’s answer, this should hold: ≤10−5. max{1,|j|}
Example
standard input standard output
4 0.3729232286
4 2 0.1379212354
0 0 1.3663189952
2 0 0.2636965438
2 2
0 2
3 1
1 -1
0 1
-1 -1
8 18
-2 1
-2 -3
-1 -4
0 -4
3 -3
4 -1
4 0
-1 2
4 1
99999998 99999999
99999999 99999998
100000000 99999999
99999999 100000000
Page 12 of 15