← 返回题目列表

Codeforces · 1912/I

I. 创新洗衣机

中文机器翻译题面 查看原题

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

Innovative Washing Machine - 原题 PDF 第 1 页
原题PDF第11页
Innovative Washing Machine - 原题 PDF 第 2 页
原题PDF第12页
可复制的 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