Background

The Lost Bamboo Forest is a bamboo grove filled with towering, endless bamboo. Because of the special terrain, all bamboo grows leaning toward the same side. Since the leaves at the tops of the bamboo are interwoven, even if the lower parts have been cut off, they still cannot fall due to interactions with other bamboo.

As the pavilion master of Hakugyokurou and its actual steward, Konpaku Youmu often needs to collect some bamboo to repair bamboo furniture and bamboo buildings. Because she has superb sword skills, she can cut down a large area of bamboo instantly as materials. Of course, Youmu does not want to have too much bamboo. So she will choose a polygonal region to collect from. At that moment, Youmu will use Roukanken to cut along the edges of the polygon.

However, since there are simply too many fallen bamboo pieces, Youmu has no time to count how much bamboo she cut. Can you help her?

Background

Problem Description

The bamboo that Youmu selects in the Lost Bamboo Forest can be considered to lie on the same plane. The bamboo can be considered to have $+\infty$ stalks, with equal spacing between any two adjacent stalks, and each stalk has the same tilt. The height of the bamboo can be considered infinite.

Youmu chooses a polygonal region and cuts the bamboo. Only the parts inside the polygon will be collected. The polygon has $n$ edges. To avoid ambiguity, it is guaranteed that no edge is parallel to the bamboo; it is also guaranteed that the polygon is a simple polygon.

We will use two real numbers $\theta$ and $a$ to describe the bamboo. The meanings of these two letters can be referenced in the figure below:

Now Youmu needs to know the total length of the bamboo she cut, that is, find the sum of the lengths of these bamboo segments (the orange segments in the figure).

Input Format

• The first line contains a positive integer $n$, denoting the number of edges of the polygon.
• The next $n$ lines give the coordinates of the $n$ vertices of the polygon in clockwise order. Vertex $i$ is connected to vertex $i+1$ $(1\le i<n)$, and vertex $n$ is connected to vertex $1$.
• Then the parameters $\theta$ and $a$ describing the segments are given.

Output Format

• One line containing one real number, denoting the total length of the bamboo. Your answer $\mathit{ans}$ is considered correct if and only if it satisfies $\dfrac{|\mathit{ans}-\mathit{std}\ |}{\max(1.0,\mathit{std}\ )}\le 10^{-6}$ with the standard answer $\mathit{std}$.

4
2.0000 2.0000
2.0000 -2.0000
-2.0000 -2.0000
-2.0000 2.0000
45.0000 1.0000

22.6274169980

8
0.0000 2.5000
1.0000 1.5000
2.5000 1.0000
2.0000 -1.0000
1.0000 -2.0000
-2.0000 -2.0000
-2.5000 1.0000
-1.0000 2.0000
60.0000 0.8000

23.1662217484

Hint

Explanation for Sample 1

It is easy to see that the total bamboo length (i.e., the total length of the orange-red segments) is $16\sqrt 2$.

Explanation for Sample 2

I have an ingenious method to explain Sample $2$, but this space is too small to write it down.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special Property} & \textbf{Score}\cr\hline 1 & 10 & \text{A} & 30 \cr\hline 2 & 10^3 & - & 20 \cr\hline 3 & 10^5 & \text{B} & 20 \cr\hline 4 & 10^5 & - & 30 \cr\hline \end{array}$$

Special Property $\textbf{A}$: It is guaranteed that $\theta\in[80,100);|x_i|,|y_i|\le 10$。
Special Property $\textbf{B}$: It is guaranteed that $\theta=90$。

• For $100\%$ of the data, it is guaranteed that $3\le n\le 10^5;|x_i|,|y_i|\le 10^4;\theta\in[1,179);a\in[0.1,100]$. All floating-point numbers in the input keep four digits after the decimal point.

Translated by ChatGPT 5