[Mirror] VNOI Cup 2022 - Final
Points: 100
You are given an undirected graph with ~n~ vertices and ~m~ edges, in which no edges connect a node to itself, as well as no pair of nodes are connected by more than one edge. Initially, each node in the graph is colored white. Your task is to color some nodes blue, such that ~q~ requirements are satisfied, the ~i~-th requirement stating that the shortest distance from node ~c_i~ to any blue node (possibly itself) is exactly ~d_i~.
Input
The first line contains three integers ~n~, ~m~ and ~q~ (~1 \le q \le n \le 5 \times 10^5~, ~0 \le m \le 5 \times 10^5~), denoting the number of nodes, the number of edges, and the number of requirements, respectively.
Each of the next ~m~ lines contains two integers ~u~ and ~v~ (~1 \le u, v \le n~, ~u \ne v~), denoting an edge between the two nodes ~u~ and ~v~. It is guaranteed that no pair of nodes are connected by more than one edge.
The next ~q~ lines, the ~i~-th of which contains two integers ~c_i~ and ~d_i~ (~1 \le c_i \le n~, ~0 \le d_i < n~) denoting the ~i~-th condition: the shortest distance from node ~c_i~ to any blue node (possibly itself) is exactly ~d_i~. It is guaranteed that each node appears in at most one condition.
Output
If there does not exist a coloring satisfying all requirements, output
NO
.
Otherwise, output YES
on the first line. On the second line, output a
single integer ~k~, the number of nodes to be colored blue. The third
line, output ~k~ integers ~p_1, p_2, \ldots, p_k~ (~p_i \ne p_j~ for
~i \ne j~), the indices of the nodes to be colored blue.
If there are multiple valid colorings, you may output any.
Scoring
Not the final scoring
Subtask 1 (~10~ points): ~n \le 16~.
Subtask 2 (~20~ points): ~n \le 5000~.
Subtask 3 (~70~ points): No additional constraints
The total score for this problem is ~100~.
Sample Input 1
7 8 3
1 2
2 3
3 4
4 1
4 5
5 6
6 4
5 7
7 2
4 1
2 1
Sample Output 1
YES
2
1 6
Sample Input 2
4 3 1
1 2
2 3
3 1
4 0
Sample Output 2
YES
2
1 4
Sample Input 3
3 3 1
1 2
2 3
3 1
1 2
Sample Output 3
NO
Notes
In the first example, we can color two nodes ~1~ and ~6~ blue:
From node ~7~, the closest blue node is node ~6~ can be reached by following the path ~7 \rightarrow 5 \rightarrow 6~.
From node ~4~, the closest blue node is node ~1~ can be reached by following the path ~4 \rightarrow 1~.
From node ~2~, the closest blue node is node ~1~ can be reached by following the path ~2 \rightarrow 1~.

Illustration of the first sample.
Another solution would be to color the nodes ~3~ and ~6~ blue.
In the second example, we can color the node ~4~ blue. The other nodes can be colored arbitrarily.

Illustration of the second sample.
In the third example, the distance from node ~1~ to both of the other two nodes is ~1~, therefore it is impossible to color a node such that the closest distance from ~1~ to a blue node is exactly ~2~.
Points: 100
You are given an integer ~n~. Construct an array ~a~ of positive integers satisfying the following requirements:
The elements of ~a~ do not exceed ~n + 1~.
All the elements of ~a~ are distinct.
For each ~x~ from ~2~ to ~n~, there exists a pair of indices ~(i, j)~ such that ~i \neq j~ and ~a_i \equiv a_j \pmod x~.
The length of ~a~ is as small as possible.
Input
The input contains a single integer ~n~ (~2 \le n \le 10^5~).
Output
In the first line, output a single integer ~k~ – the length of the constructed array ~a~.
In the second line, output ~k~ integers ~a_1, a_2, \ldots, a_k~. The array must satisfy all requirements in the statement.
If there are multiple possible answers, output any.
Scoring
Subtask 1 (~10~ points): ~n \le 16~.
Subtask 2 (~90~ points): No additional constraints
The total score for this problem is ~100~.
Sample Input 1
5
Sample Output 1
4
1 3 5 6
Notes
It can be easily seen that the array ~[1, 3, 5, 6]~ satisfies the first two requirements. We show that it satisfies the third requirement as well:
The pair of values ~1~ and ~5~ both has remainder ~1~ when divided by ~x = 2~.
The pair of values ~3~ and ~6~ are both divisible by ~x = 3~.
The pair of values ~1~ and ~5~ both has remainder ~1~ when divided by ~x = 4~.
The pair of values ~1~ and ~6~ both has remainder ~1~ when divided by ~x = 5~.
It can be shown that, for ~n = 5~, there exists no array ~a~ with length less than ~4~ satisfying all requirements.
Points: 100
Lục bát is a Vietnamese form of poem. As its Sino-Vietnamese namesake implies, a pair of lines in this poem contains one six-syllable line, and one eight-syllable line, rhyming with each other. A lục bát poem consists of many pairs of lines following said rule, without limits on the number of lines. Lục bát poem is a very popular form of poem in Vietnam, due to having simple rules, but is very easy to reminiscent in one's memory.
Specifically, in this problem, we define a lục bát poem as follow:
The poem has ~2 \cdot n~ lines, in which ~n~ of the lines are six-syllable, and ~n~ of the lines are eight-syllable.
The six-syllable lines will be in positions 1, 3, 5, ~\ldots~
The eight-syllable lines will be in positions 2, 4, 6, ~\ldots~
Each line's last syllable must rhyme with the sixth syllable of its following line.
Two lines are considered to rhyme with each other if the multiset of vowels (the letters
a
,e
,i
,o
vàu
) of those two words are the same.
You are given ~n~ six-syllable lines and ~n~ eight-syllable lines, arrange these lines into a lục bát poem.
Input
The first line contains a single integer ~n~ (~1 \le n \le 10^5~), denoting the number of six-syllable lines and eight-syllable lines.
The ~i~-th line out of the next ~n~ lines each contain ~6~ words belonging to a six-syllable line.
The ~i~-th line out of the next ~n~ lines each contain ~8~ words belonging to a eight-syllable line.
Each word consists of only lowercase latin letters. The sum of length of all words do not exceed ~10^7~.
Output
If it is impossible to arrange these ~2n~ lines into a single poem
following the rule, output NO
.
Otherwise, output YES
on the first line. On the following ~2n~ lines,
output the poem.
Scoring
Subtask 1 (~10~ points): ~n \le 6~.
Subtask 2 (~90~ points): No additional constraints
The total score for this problem is ~100~.
Sample Input 1
2
nhi vang bong trang la xanh
trong dam gi dep bang sen
gan bun ma chang hoi tanh mui bun
la xanh bong trang lai chen nhi vang
Sample Output 1
YES
trong dam gi dep bang sen
la xanh bong trang lai chen nhi vang
nhi vang bong trang la xanh
gan bun ma chang hoi tanh mui bun
Sample Input 2
3
trai qua mot cuoc be dau
la gi bi sac tu phong
tram nam trong coi nguoi ta
troi xanh quen thoi ma hong danh ghen
chu tai chu menh kheo la ghet nhau
nhung dieu trong thay ma dau don long
Sample Output 2
YES
tram nam trong coi nguoi ta
chu tai chu menh kheo la ghet nhau
trai qua mot cuoc be dau
nhung dieu trong thay ma dau don long
la gi bi sac tu phong
troi xanh quen thoi ma hong danh ghen
Points: 150
This is an interactive problem.
Tài and his brother really takes play the number-making game. Firstly, they will pick a prime number ~n~. Then they both prepare ~n~ blank pieces of paper and arrange them horizontally. The papers are numbered ~1~ to ~n~ from right to left.
The game goes as follow. Two brothers will take turns, with Tài going first. On their turn, the player will pick a blank piece of paper that hasn't been written on, then write a single digit from ~0~ to ~9~ of their choice. The game ends when all of the papers have been written on.
Tài is learning algebra, and is much interested in divisibility of numbers. Therefore Tài wants that after the game ends, the number obtained by reading the digits on the papers from left to right will be divisible by ~n~. Tài's brother on the other hand, wanting to add some friendly competitiveness to be game, will actively try to make the resulting number not divisible by ~n~.
Given the number ~n~ that the brothers picked, help Tài win the game by creating a number divisible by ~n~. Note that it is allowed that the resulting number may have leading zeroes.
Interaction
In this problem, you will play as Tài, and the jury will play as his brother.
The jury program will first print a single integer ~t~ (~1 \le t \le 10~), the number of game matches. Each match will happen as follow.
The jury program first prints a single integer ~n~ (~1 \le n \le 100\,000~, ~n~ is a prime number), the integer that the brothers picked.
Then you and the jury program will, ~n~ times in total, take turns printing two integers ~p~ and ~d~ (~1 \le p \le n~, ~0 \le d \le 9~), denoting on their respective turn, the player chooses to fill in the digit ~d~ into the paper indexed ~p~ from right to left.
After making ~n~ turns in total, the jury outputs a single integer ~x~ denoting the result. If the number created is indeed divisible by ~n~, the jury program outputs ~x = 1~. Afterwards you can proceed with the next match (if any). If the number created is not divisible by ~n~, the jury program outputs ~x = 0~, and will not provide you with additional inputs from that point onwards. In such case, your program must terminate to receive a Wrong answer
verdict, otherwise it may receive arbitrary verdict.
After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Time Limit Exceeded
. To do this, use:
fflush(stdout)
orcout.flush()
in C++;System.out.flush()
in Java;flush(output)
in Pascal;stdout.flush()
in Python;- see documentation for other languages.
Scoring
Subtask 1 (~30~ points): ~n < 10~.
Subtask 2 (~120~ points): No additional constraints
The total score for this problem is ~150~.
Sample 1
Jury's program | Participant's program |
---|---|
2 2 2 5 1 3 2 3 1 |
1 8 1 5 3 7 |
Notes
There are ~t = 2~ matches.
In the first match with ~n = 2~, Tài goes first and fills in the first paper from right to left with the digit ~8~. The digits are now:
_8
Afterwards, the jury program chooses to fill in ~5~ to the remaining sheet. The digits are now:
58
The digits on the papers read ~58~, which is divisible by ~2~. Thereby the jury program outputs ~x = 1~ and begins the next match.
In the second match with ~n = 3~, Tài goes first and fills in the first paper from right to left with the digit ~5~. The digits are now:
__5
Afterwards, the jury program chooses to fill in ~3~ to the second sheet from right to left. The digits are now:
_35
Finally, Tài chooses the digit ~7~ to fill in the final sheet. The digits are now:
735
The row of paper reads ~735~, which is ~3~ so the jury outputs ~x = 1~ and terminates. Tài emerges victorious for all the matches.
Points: 150
Lộc likes dark cyan, because of that, when Lộc registers his first
account on a mysterious Online Judge, he chose the nickname darkcyan
.
Unfortunately, this nickname was taken. The system recommends Lộc a
couple of other nicknames, some of which are darkcyan_no1
,
darkcyan_pro
and darkcyan_vip
, none of which Lộc liked at all. After
spending a few eternities pondering, the nickname chosen by Lộc was
darkkcyan
, very similar to the initial nickname, only duplication the
k
. This nickname turns out wasn't taken! So it became Lộc's new
nickname for many other different Online Judges.
Lộc finds changing nicknames like this interesting, and he applies this idea to create an entirely novel nickname suggestion system! For a nickname that's represented by a string with ~k~ characters ~t_1 t_2 \ldots t_l~, the system can change the nickname using the following operation several (possibly zero) times:
- The system selects an integer ~i~ (~1 \le i \le l~) at random. Each position has equal probability of being chosen. The system then inserts ~c~ occurrences of the character ~t_i~ right after position ~i~. The new character's indices are ~i + 1, i + 2, \ldots, i + c - 1~ and the indices of every following characters are increased by ~c~. The length of the new nickname will be ~l + c~.
The exact value of ~c~, the number of extra characters inserted, is calculated as follow:
Initially, ~c \leftarrow 1~.
The system tosses a fair coin, having 50/50 chance of landing on either sides. While the coin lands on heads, ~c~ is increased by one.
The previous step may be repeated many times. However if ~c~ has already reached the limit ~k~, the system stops at that value of ~c~.
Formally, the value ~c~ is calculated with the following pseudocode
c = 1;
while c != k and coinToss() == head:
c = c + 1;
For example, suppose the starting nickname is darkcyan
(with length
~8~) and the limit ~k = 3~.
Nickname
darkkcyan
has a creation probability of ~\frac{1}{8} \cdot 50\% = \frac{1}{16}~ (the probability of choosing the characterk
is ~\frac{1}{8}~ and the probability of the coin toss landing tails is ~50\%~). Some other nicknames such asddarkcyan
,darrkcyan
ordarkcyann
has equal probability of being created to this one.Nickname
darkkkcyan
has a creation probability of ~\frac{1}{8} \cdot 50\% \cdot 50\% = \frac{1}{32}~ (the probability of choosing the characterk
is ~\frac{1}{8}~ and the probability of the first coin toss landing heads ~50\%~, the probability of the second coin toss landing tails ~50\%~). Some other nicknames such asdddarkcyan
,darrrkcyan
ordarkcyannn
has equal probability of being created to this one.Nicknames
darkkkkcyan
,ddddarkkcyan
,darrrrkcyan
ordarkcyannnn
has a probability of creation not ~\frac{1}{64}~, but also ~\frac{1}{32}~, because at this point, ~c~ has already reached the ~k = 3~ limit.
Note: For ~k = -1~, the number of possible coin tosses is not limited.
This design uses randomization to generate new nicknames. Lộc decides to go for this design choice to reduce cost of checking nickname availability, yet the probability of generating a brand new unused nickname is very high without needing to expect too many steps in the generating process.
Lộc thinks it's a pity if there's no existing nickname recommendation system like this. So he decides to implement this system for the social network Virtual Network for Online Intercommunication (VNOI) that he's developing. On VNOI there are currently ~n~ users, the ~i~-th of which has the nickname ~S_i~. Lộc wants to know, for each nickname ~S_i~, if there is a new user who attempts to register with this nickname, what is the expected number of steps needed to transform this username into a brand new, unused username, following the aforementioned procedure. As Lộc is a very busy developing other parts of the system, he needs your help to solve this problem.
Given the list of nicknames of the ~n~ users on the system, for each nickname ~S_i~, calculate the expected number of operations to turn ~S_i~ into a new, unused nickname, on the system. To ensure your calculations are correct, output the answer modulo ~10^9 + 7~.
Formally, let ~M = 10^9 + 7~. We can show that the answer can be represented as an irreducible fraction ~\frac{p}{q}~, where ~p~ and ~q~ are integers and ~q \not \equiv 0 \pmod{M}~. Output ~p \cdot q^{-1} \bmod M~. In other words, output such an integer ~x~ that ~0 \le x < M~ and ~x \cdot q \equiv p \pmod{M}~.
Input
The first line contains two integers ~n~ and ~k~ (~1 \le n \le 10^5~, ~1 \le k \le 10^9~ or ~k = -1~), denoting the number of VNOI users and the character limit in one operation. If ~k = -1~, the number of characters that may be added in one operation is not limited.
The ~i~-th out of the next ~n~ lines each contain a single string ~S_i~ (~1 \le |S_i| \le 10^5~, ~S_i~ consists only of lowercase latin letters) denoting the nickname of the ~i~-th user.
Is it guaranteed that the total length of all nicknames do not exceed ~10^5~, and no two nicknames are the same.
Output
Output ~n~ lines. The ~i~-th line should contain the expected number of operations needed to transform nickname ~S_i~ into a nickname that has not appeared in the system, modulo ~10^9 + 7~.
Scoring
Subtask 1 (~45~ points): ~1 \le k \le 10~.
Subtask 2 (~105~ points): no additional constraints.
The total score for this problem is ~150~.
Sample Input 1
3 2
aaa
aa
a
Sample Output 1
1
500000005
250000004
Sample Input 2
2 -1
b
bbb
Sample Output 2
250000003
1
Sample Input 3
3 1
ab
aab
abb
Sample Output 3
2
1
1
Notes
In the first sample, the nickname aa
is expected to take ~\frac{3}{2}~
operations. Since the two operations are the same, we can skip the
character selection, and only look at the coin tossing process:
The probability of the result string being
aaa
would be ~50\%~ for getting tails on the first coin toss. Since this nickname has already appeared, we need another operation. Regardless of how the second operation turns out, we get a new nickname, thus the number of operations is ~2~.The probability of the result string being
aaaa
is ~50\%~ for the character addition limit is ~k = 2~. Since there is no other nickname matching this, we need ~1~ operation in this case.
Therefore the expected number of operations is ~50\% \cdot (2 + 1) = \frac{3}{2}~.
For the nickname a
in the first sample, the expected number of
operations is ~\frac{9}{4}~.
In the second sample, the number of characters that can be added in one
operation is unlimited. The nickname b
thus has the following
outcomes:
Creating the nickname
bbb
with probability ~50\% \cdot 50\% = 25\%~. In this case, we need one more operation to create a new nickname, thus the number of operations needed is ~2~.Creating the nickname other than
bbb
with probability ~1 - 25\% = 75\%~. In this case we have already obtained a new nickname, thus ~1~ is the number of operations needed.
Therefore, the expected number of operations is ~25\% \cdot 2 + 75\% \cdot 1 = \frac{5}{4}~.
Points: 200
This is an interactive problem.
~\textit{ngfam}~ has a quantum supercomputer peculiarly structures with ~n~ quantum gates numbered from ~1~ to ~n~. The ~i~-th quantum gate has a characteristic parameter ~c_i~ ~(0 \leq c_i \leq 100)~.
To use the supercomputer, the user needs to input a non-negative integer ~a~. At the same time, the computer initializes a variable ~x = 1~. Afterwards, the quantum gates from ~1~ to ~n~ will be activated sequentially. When activating the ~i~-th gate, the computer changes ~x~ according to one of the following possibilities:
~x \leftarrow (x \times a) \bmod 998\,244\,353~
~x \leftarrow (x \times c_i) \bmod 998\,244\,353~
in which ~a \bmod b~ denoting the remainder of ~a~ when divided by ~b~.
Each outcome has the same probability of happening, and there are totally ~2^n~ outcomes in the activation process of all quantum gates. However, since this is a quantum supercomputer, so instead of returning a specific value of ~x~, it returns the overloaded value of ~x~, equivalent to the expected value of ~x~ for all possible scenarios.
As the creator of the supercomputer, ~\textit{ngfam}~ has initialized the ~c_i~ parameter of the ~n~ gates to his liking, but ~\textit{ngfam}~ won't be telling you this info. On the other hand, ~\textit{ngfam}~ will let you play with his computer ~2 \cdot n~ times: you can pick the parameters ~a~ you want, and the computer returns the corresponding ~x~. When you're done, ~\textit{ngfam}~ wants to make sure that you understand what's going on in his supercomputer, therefore you need to answer to ~\textit{ngfam}~ ~q~ of the same questions from ~\textit{ngfam}~ without using his computer this time.
Note that the overloaded value itself may not be an integer, but the computer will return said value modulo ~998\,244\,353~.
Formally, let ~M = 998\,244\,353~ and the overloaded value is an irreducible fraction ~\frac{p}{q}~, where ~p~ and ~q~ are integers and ~q \not \equiv 0 \pmod{M}~. The computer returns ~p \cdot q^{-1} \bmod M~. In other words, the computer returns such an integer ~r~ that ~0 \le r < M~ and ~r \cdot q \equiv p \pmod{M}~.
Input
The first line contains two integers ~n~ and ~q~ (~1\le n \le 50\,000~, ~1 \le q \le 50~) denoting the number of quantum gates, and the number of questions you should answer, respectively.
Afterwards you should interact with the jury program.
Interaction
You are allowed to pose a maximum of ~2 \cdot n~ questions, each question must be printed by the form ? a
(~0 \leq a < 998\,244\,353~). The jury responds with a single integer, that is the overloaded value of ~x~ after using the value ~a~.
When you're done, output on a single line !
denoting you are ready to answer questions.
Afterwards, you have to answer ~q~ questions from ~\textit{ngfam}~. For each question, the jury program gives you a single integer ~a~ (~0 \le a \le 998\,244\,353~). You need to calculate and provide the overloaded value of ~x~ that the computer would've returned if supplied with said value ~a~. You have to answer the questions sequentially, meaning you won't receive the next question (if any) without answering the current one first.
After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Time Limit Exceeded
. To do this, use:
fflush(stdout)
orcout.flush()
in C++;System.out.flush()
in Java;flush(output)
in Pascal;stdout.flush()
in Python;- see documentation for other languages.
Scoring
Subtask 1 (~20~ points): ~n \le 50~ and ~1 \le c_i \le 2~.
Subtask 2 (~60~ points): ~n \le 50~.
Subtask 3 (~120~ points): No additional constraints.
The total score for this problem is ~200~.
Sample 1
Jury's program | Participant's program |
---|---|
2 2 5 499122184 1 2 |
? 3 ? 4 ! 499122178 3 |
Sample 2
Jury's program | Participant's program |
---|---|
1 5 3 1 2 3 4 5 |
? 1 ! 3 499122180 4 499122181 5 |
Notes
In the first sample, the distinctive parameters of the quantum gates are ~c_1 = 1~ and ~c_2 = 2~. The two questions asked were ~a = 3~ and ~a = 4~. For ~a = 3~, the following possibilities exist:

Therefore for ~a = 3~, the different possible values of ~x~ are ~[9, 6, 3, 2]~, and the expected value of ~x~ is ~\frac{9 + 6 + 3 + 2} {2^2} = \frac{20} {4} = 5~
For ~a = 4~, the possible values are:
~1 \times a \times a = 1 \times 4 \times 4 = 16~
~1 \times a \times c_2 = 1 \times 4 \times 2 = 8~
~1 \times c_1 \times a = 1 \times 1 \times 4 = 4~
~1 \times c_1 \times c_2 = 1 \times 1 \times 2 = 2~
The overloaded value of ~x~ on this computer for ~a = 4~ would be ~\frac{16 + 8 + 4 + 2} {2^2} = \frac{30}{4} = \frac{15}{2}~. The output is ~499122184~ since ~499122184 \times 2 \equiv 15 \bmod (998\,244\,353)~.
For ~a = 1~, the different possible values of ~x~ are ~[1, 2, 1, 2]~, and for ~a = 2~, the different possible values of ~x~ are ~[4, 4, 2, 2]~.
In the second example, the distinctive parameter of the only quantum gate is ~c_1 = 5~.
Points: 200
The lower envelope of a set of ~n~ lines, in which the ~i~-th line has the equation ~y_i = a_i \cdot x + b_i~, has the graphical representation ~y = \min_{i = 1}^n\{ a_i \cdot x + b_i \}~.
We call the vertices of a lower envelope the points that lie on the lower envelope that are also the intersection of two different segments in the set. Let us suppose that the lower envelope has ~k~ vertices ~p_1, p_2, \ldots, p_k~, with vertex ~p_i~ at a smaller x-coordinate than ~p_{i + 1}~ (~1 \le i < k~). We call the perimeter of the lower envelope being the sum of distances between every two consecutive vertices of the lower envelope, formally ~p_1 p_2 + p_2 p_3 + \ldots p_{k - 1} p_k~. If the lower envelope contains less than two vertices, we consider the perimeter to be ~0~.

The lower envelope is colored orange. It has three vertices ~p_1~, ~p_2~ and ~p_3~. The perimeter is denoted by the continuous orange segment.
You are given ~n~ lines. For each line, find the perimeter of the lower envelope created by the remaining ~n - 1~ lines.
Input
The first line contains an integer ~n~ (~2 \le n \le 100\, 000~), the number of lines.
The ~i~-th out of the next ~n~ lines contains two integers ~a_i~ và ~b_i~ (~|a_i|, |b_i| \le 10^9~), the parameters of the ~i~-th line.
It is guaranteed that there are no two lines that are the same.
Output
Output ~n~ lines. The ~i~-th of which contains the perimeter of the lower envelope made by the other ~n - 1~ lines, that is, excluding line ~i~.
Your answer is considered correct if its absolute or relative error does not exceed ~10^{-6}~.
Formally, let your answer be ~a~, and the jury's answer be ~b~. Your answer is accepted if and only if ~\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}~.
Scoring
Subtask 1 (~30~ points): ~n \le 100~.
Subtask 2 (~40~ points): ~n \le 1000~.
Subtask 3 (~130~ points): No additional constraints.
The total score for this problem is ~200~.
Sample Input 1
4
0 0
0 1
1 0
-1 3
Sample Output 1
1.0
3.0
0
0
Sample Input 2
5
4 21
-3 -13
1 -3
3 15
1 -1
Sample Output 2
9.1923881554
0.0000000000
6.1282587703
7.7781745931
7.7781745931
Notes
Below is the illustration for sample 1.

The first line has the equation ~y = 0x + 0~ colored red. Excluding this line, the lower envelope has vertices ~B~ và ~C~.
The second line has the equation ~y = 0x + 1~ colored blue. Excluding this line, the lower envelope has vertices ~A~ và ~D~.
The third line has the equation ~y = x~ colored green. Excluding this line, the lower envelope has vertices ~D~.
The fourth line has the equation ~y = -x + 3~ colored purple. Excluding this line, the lower envelope has vertices ~A~.