apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$ of length at most $$$\mathbf{8}$$$.

For each string $$$s_i$$$, determine if there exist two strings $$$s_j$$$ and $$$s_k$$$ such that $$$s_i = s_j + s_k$$$. That is, $$$s_i$$$ is the concatenation of $$$s_j$$$ and $$$s_k$$$. Note that $$$j$$$ can be equal to $$$k$$$.

Recall that the concatenation of strings $$$s$$$ and $$$t$$$ is $$$s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$$$, where $$$p$$$ and $$$q$$$ are the lengths of strings $$$s$$$ and $$$t$$$ respectively. For example, concatenation of "code" and "forces" is "codeforces".

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of strings.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains non-empty string $$$s_i$$$ of length at most $$$\mathbf{8}$$$, consisting of lowercase English letters. Among the given $$$n$$$ strings, there may be equal (duplicates).

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, output a binary string of length $$$n$$$. The $$$i$$$-th bit should be $$$\texttt{1}$$$ if there exist two strings $$$s_j$$$ and $$$s_k$$$ where $$$s_i = s_j + s_k$$$, and $$$\texttt{0}$$$ otherwise. Note that $$$j$$$ can be equal to $$$k$$$.

## Examples
```input
3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code
```
```output
10100
011
10100101
```

## Note
In the first test case, we have the following:

- $$$s_1 = s_2 + s_2$$$, since $$$\texttt{abab} = \texttt{ab} + \texttt{ab}$$$. Remember that $$$j$$$ can be equal to $$$k$$$.
- $$$s_2$$$ is not the concatenation of any two strings in the list.
- $$$s_3 = s_2 + s_5$$$, since $$$\texttt{abc} = \texttt{ab} + \texttt{c}$$$.
- $$$s_4$$$ is not the concatenation of any two strings in the list.
- $$$s_5$$$ is not the concatenation of any two strings in the list.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a square grid with $$$n$$$ rows and $$$n$$$ columns. Each cell contains either $$$0$$$ or $$$1$$$.

In an operation, you can select a cell of the grid and flip it (from $$$0 \to 1$$$ or $$$1 \to 0$$$). Find the minimum number of operations you need to obtain a square that remains the same when rotated $$$0^{\circ}$$$, $$$90^{\circ}$$$, $$$180^{\circ}$$$ and $$$270^{\circ}$$$.

The picture below shows an example of all rotations of a grid.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the size of the grid.

Then $$$n$$$ lines follow, each with $$$n$$$ characters $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1$$$) — the number written in each cell.

## Output Format
For each test case output a single integer  — the minimum number of operations needed to make the square look the same rotated $$$0^{\circ}$$$, $$$90^{\circ}$$$, $$$180^{\circ}$$$ and $$$270^{\circ}$$$.

## Examples
```input
5
3
010
110
010
1
0
5
11100
11011
01011
10011
11000
5
01000
10101
01010
00010
01001
5
11001
00000
11111
10110
01111
```
```output
1
0
9
7
6
```

## Note
In the first test case, we can perform one operations to make the grid $$$\begin{matrix}0 & 1 & 0\\ 1 & 1 & \color{red}{1}\\ 0 & 1 & 0\end{matrix}$$$. Now, all rotations of the square are the same.

In the second test case, all rotations of the square are already the same, so we don't need any flips.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a_1, a_2, \dots a_n$$$. Count the number of pairs of indices $$$1 \leq i, j \leq n$$$ such that $$$a_i < i < a_j < j$$$.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the number of pairs of indices satisfying the condition in the statement.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

## Examples
```input
5
8
1 1 2 3 8 2 1 4
2
1 2
10
0 2 1 6 3 4 1 2 8 3
2
1 1000000000
3
0 1000000000 2
```
```output
3
0
10
0
1
```

## Note
For the first test cases the pairs are $$$(i, j)$$$ = $$$\{(2, 4), (2, 8), (3, 8)\}$$$.

- The pair $$$(2, 4)$$$ is true because $$$a_2 = 1$$$, $$$a_4 = 3$$$ and $$$1 < 2 < 3 < 4$$$.
- The pair $$$(2, 8)$$$ is true because $$$a_2 = 1$$$, $$$a_8 = 4$$$ and $$$1 < 2 < 4 < 8$$$.
- The pair $$$(3, 8)$$$ is true because $$$a_3 = 2$$$, $$$a_8 = 4$$$ and $$$2 < 3 < 4 < 8$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mainak has an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ positive integers. He will do the following operation to this array exactly once:

- Pick a subsegment of this array and cyclically rotate it by any amount.

- Pick two integers $$$l$$$ and $$$r$$$, such that $$$1 \le l \le r \le n$$$, and any positive integer $$$k$$$.
- Repeat this $$$k$$$ times: set $$$a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l$$$ (all changes happen at the same time).

Mainak wants to maximize the value of $$$(a_n - a_1)$$$ after exactly one such operation. Determine the maximum value of $$$(a_n - a_1)$$$ that he can obtain.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 50$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 999$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

## Output Format
For each test case, output a single integer — the maximum value of $$$(a_n - a_1)$$$ that Mainak can obtain by doing the operation exactly once.

## Examples
```input
5
6
1 3 9 11 5 7
1
20
3
9 99 999
4
2 1 8 1
3
2 1 5
```
```output
10
0
990
7
4
```

## Note
- In the first test case, we can rotate the subarray from index $$$3$$$ to index $$$6$$$ by an amount of $$$2$$$ (i.e. choose $$$l = 3$$$, $$$r = 6$$$ and $$$k = 2$$$) to get the optimal array: $$$$$$[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]$$$$$$ So the answer is $$$a_n - a_1 = 11 - 1 = 10$$$.
- In the second testcase, it is optimal to rotate the subarray starting and ending at index $$$1$$$ and rotating it by an amount of $$$2$$$.
- In the fourth testcase, it is optimal to rotate the subarray starting from index $$$1$$$ to index $$$4$$$ and rotating it by an amount of $$$3$$$. So the answer is $$$8 - 1 = 7$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mainak has two positive integers $$$n$$$ and $$$m$$$.

Mainak finds a sequence $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ positive integers interesting, if for all integers $$$i$$$ ($$$1 \le i \le n$$$), the bitwise XOR of all elements in $$$a$$$ which are strictly less than $$$a_i$$$ is $$$0$$$. Formally if $$$p_i$$$ is the bitwise XOR of all elements in $$$a$$$ which are strictly less than $$$a_i$$$, then $$$a$$$ is an interesting sequence if $$$p_1 = p_2 = \ldots = p_n = 0$$$.

For example, sequences $$$[1,3,2,3,1,2,3]$$$, $$$[4,4,4,4]$$$, $$$[25]$$$ are interesting, whereas $$$[1,2,3,4]$$$ ($$$p_2 = 1 \ne 0$$$), $$$[4,1,1,2,4]$$$ ($$$p_1 = 1 \oplus 1 \oplus 2 = 2 \ne 0$$$), $$$[29,30,30]$$$ ($$$p_2 = 29 \ne 0$$$) aren't interesting.

Here $$$a \oplus b$$$ denotes bitwise XOR of integers $$$a$$$ and $$$b$$$.

Find any interesting sequence $$$a_1, a_2, \ldots, a_n$$$ (or report that there exists no such sequence) such that the sum of the elements in the sequence $$$a$$$ is equal to $$$m$$$, i.e. $$$a_1 + a_2 \ldots + a_n = m$$$.

As a reminder, the bitwise XOR of an empty sequence is considered to be $$$0$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line and the only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^9$$$) — the length of the sequence and the sum of the elements.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, if there exists some interesting sequence, output "Yes" on the first line, otherwise output "No". You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

If the answer is "Yes", output $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \ge 1$$$), forming an interesting sequence such that $$$a_1 + a_2 \ldots + a_n = m$$$. If there are multiple solutions, output any.

## Examples
```input
4
1 3
6 12
2 1
3 6
```
```output
Yes
3
Yes
1 3 2 2 3 1
No
Yes
2 2 2
```

## Note
- In the first test case, $$$[3]$$$ is the only interesting sequence of length $$$1$$$ having sum $$$3$$$.
- In the third test case, there is no sequence of length $$$2$$$ having sum of elements equal to $$$1$$$, so there is no such interesting sequence.
- In the fourth test case, $$$p_1 = p_2 = p_3 = 0$$$, because bitwise XOR of an empty sequence is $$$0$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence $$$s$$$ of length $$$2 n$$$.

Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of $$$2 n$$$ vertices using the balanced bracket sequence $$$s$$$. For any two distinct vertices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le 2 n$$$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment $$$s[i \ldots j]$$$ forms a balanced bracket sequence.

Determine the number of connected components in Topshe's graph.

See the Notes section for definitions of the underlined terms.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of opening brackets in string $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$2 n$$$ — a balanced bracket sequence consisting of $$$n$$$ opening brackets "(", and $$$n$$$ closing brackets ")".

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, output a single integer — the number of connected components in Topshe's graph.

## Examples
```input
4
1
()
3
()(())
3
((()))
4
(())(())
```
```output
1
2
3
3
```

## Note
Sample explanation:

In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes $$$1$$$ and $$$2$$$ connected by a single edge.

In the second test case, the graph constructed from the bracket sequence ()(()) would be the following (containing two connected components):

Definition of Underlined Terms:

- A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $$$+$$$ and $$$1$$$. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.
- The subsegment $$$s[l \ldots r]$$$ denotes the sequence $$$[s_l, s_{l + 1}, \ldots, s_r]$$$.
- A connected component is a set of vertices $$$X$$$ such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to $$$X$$$ violates this rule.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a connected, undirected and unweighted graph with $$$n$$$ vertices and $$$m$$$ edges. Notice the limit on the number of edges: $$$m \le n + 2$$$.

Let's say we color some of the edges red and the remaining edges blue. Now consider only the red edges and count the number of connected components in the graph. Let this value be $$$c_1$$$. Similarly, consider only the blue edges and count the number of connected components in the graph. Let this value be $$$c_2$$$.

Find an assignment of colors to the edges such that the quantity $$$c_1+c_2$$$ is minimised.

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n-1 \leq m \leq \min{\left(n+2,\frac{n \cdot (n-1)}{2}\right)}$$$) — the number of vertices and the number of edges respectively.

$$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$) denoting that the $$$i$$$-th edge goes between vertices $$$u_i$$$ and $$$v_i$$$. The input is guaranteed to have no multiple edges or self loops. The graph is also guaranteed to be connected.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$. It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

## Output Format
For each test case, output a binary string of length $$$m$$$. The $$$i$$$-th character of the string should be 1 if the $$$i$$$-th edge should be colored red, and 0 if it should be colored blue. If there are multiple ways to assign colors to edges that give the minimum answer, you may output any.

## Examples
```input
4
5 7
1 2
2 3
3 4
4 5
5 1
1 3
3 5
4 4
1 2
2 3
1 4
3 4
6 7
1 2
1 3
3 4
4 5
1 4
5 6
6 2
2 1
1 2
```
```output
0111010
1001
0001111
0
```

## Note
- The corresponding graph of the first test case is:  $$$c_1 + c_2 = 1 + 2 = 3$$$
- The corresponding graph of the second test case is:  $$$c_1 + c_2 = 2 + 2 = 4$$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation $$$p$$$ of length $$$n$$$ is called almost perfect if for all integer $$$1 \leq i \leq n$$$, it holds that $$$\lvert p_i - p^{-1}_i \rvert \le 1$$$, where $$$p^{-1}$$$ is the inverse permutation of $$$p$$$ (i.e. $$$p^{-1}_{k_1} = k_2$$$ if and only if $$$p_{k_2} = k_1$$$).

Count the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of each test case follows.

The first and only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the length of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the number of almost perfect permutations of length $$$n$$$ modulo $$$998244353$$$.

## Examples
```input
3
2
3
50
```
```output
2
4
830690567
```

## Note
For $$$n = 2$$$, both permutations $$$[1, 2]$$$, and $$$[2, 1]$$$ are almost perfect.

For $$$n = 3$$$, there are only $$$6$$$ permutations. Having a look at all of them gives us:

- $$$[1, 2, 3]$$$ is an almost perfect permutation.
- $$$[1, 3, 2]$$$ is an almost perfect permutation.
- $$$[2, 1, 3]$$$ is an almost perfect permutation.
- $$$[2, 3, 1]$$$ is NOT an almost perfect permutation ($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2$$$).
- $$$[3, 1, 2]$$$ is NOT an almost perfect permutation ($$$\lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2$$$).
- $$$[3, 2, 1]$$$ is an almost perfect permutation.

So we get $$$4$$$ almost perfect permutations.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mainak has a convex polygon $$$\mathcal P$$$ with $$$n$$$ vertices labelled as $$$A_1, A_2, \ldots, A_n$$$ in a counter-clockwise fashion. The coordinates of the $$$i$$$-th point $$$A_i$$$ are given by $$$(x_i, y_i)$$$, where $$$x_i$$$ and $$$y_i$$$ are both integers.

Further, it is known that the interior angle at $$$A_i$$$ is either a right angle or a proper obtuse angle. Formally it is known that:

- $$$90 ^ \circ \le \angle A_{i - 1}A_{i}A_{i + 1} < 180 ^ \circ$$$, $$$\forall i \in \{1, 2, \ldots, n\}$$$ where we conventionally consider $$$A_0 = A_n$$$ and $$$A_{n + 1} = A_1$$$.

Mainak's friend insisted that all points $$$Q$$$ such that there exists a chord of the polygon $$$\mathcal P$$$ passing through $$$Q$$$ with length not exceeding $$$1$$$, must be coloured $$$\color{red}{\text{red}}$$$.

Mainak wants you to find the area of the coloured region formed by the $$$\color{red}{\text{red}}$$$ points.

Formally, determine the area of the region $$$\mathcal S = \{Q \in \mathcal{P}$$$ | $$$Q \text{ is coloured } \color{red}{\text{red}}\}$$$.

Recall that a chord of a polygon is a line segment between two points lying on the boundary (i.e. vertices or points on edges) of the polygon.

## Input Format
The first line contains an integer $$$n$$$ ($$$4 \le n \le 5000$$$) — the number of vertices of a polygon $$$\mathcal P$$$.

The $$$i$$$-th line of the next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of $$$A_i$$$.

Additional constraint on the input: The vertices form a convex polygon and are listed in counter-clockwise order. It is also guaranteed that all interior angles are in the range $$$[90^\circ ; 180^\circ )$$$.

## Output Format
Print the area of the region coloured in $$$\color{red}{\text{red}}$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

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^{-4}$$$.

## Examples
```input
4
4 5
4 1
7 1
7 5
```
```output
1.17809724510
```
-----
```input
5
-3 3
3 1
4 2
-1 9
-2 9
```
```output
1.07823651333
```

## Note
In the first example, the polygon $$$\mathcal P$$$ can be visualised on the Cartesian Plane as:

Now solve the problem and return the code.