P7778 'JROI-2' Dancing Line

> If you let the music walk along a straight line, then your eyes are infinite. k Tian likes playing Dancing Line. k Tian decided to make a Dancing Line level by himself.

Note: This problem does not consider special turning methods such as “maze”, teleport lines such as “football”, or jumping and landing such as “piano”. As everyone knows, the path in Dancing Line is a polyline. Each click will make the moving direction rotate **$90^\circ$ clockwise or counterclockwise**, and **the rotation directions of any two adjacent rotations are different**. For example, the following are valid paths (the path **does not have to follow the grid of the Cartesian coordinate system**):   And the following are invalid paths: The rotation angle is not $90^\circ$:  Turning left twice in a row:  A path that obviously does not meet the requirements:  k Tian placed the path into a 2D coordinate system and wrote down the coordinates of the path’s **start point**, **end point**, and **turning points** (both coordinates are **integers**). He put them into a file and left. When k Tian came back and turned on his computer, he found that all the data in his file was messed up. The coordinates of the points were no longer stored in the original order, but were arranged in a strange order. k Tian wants to reconstruct the path from these data. He also wants to estimate the difficulty of this level, denoted by $s$: $$s=\sum\limits_{i=1}^{n}{t_i^2},t_i=\dfrac{d(P_{i-1},P_i)}{v}$$ Where: - $P_i(0\leq i\leq n)$ denotes the $i$-th point of the **reconstructed** path starting from the start point (the start point is $P_0$, and the end point is $P_n$). - $v$ is the line speed, a given **positive integer**. - $d(A,B)$ denotes the distance between points $A$ and $B$ in the coordinate system. Can you help him?

The first line contains two positive integers $n,v$, with meanings as described above. The next $n+1$ lines each contain two integers, representing the coordinates of each point in the file **before reconstruction**.

Output one number $s$ as described above, and output its value modulo $998244353$. More specifically, suppose $s$ in lowest terms is $\dfrac{x}{y}$. You need to output the smallest non-negative integer satisfying $ys\equiv x\pmod{998244353}$. In this problem, you should output $x\times y^{998244351}\bmod 998244353$.

**Explanation of the samples** For Sample 1, the path is as follows:  The lengths of the segments are $2\sqrt{5},2\sqrt{5},\sqrt{5},3\sqrt{5},2\sqrt{5},\sqrt{5},4\sqrt{5},2\sqrt{5}$. The value of $s$ is $53\dfrac{3}{4}$, and the result after taking modulo is $249561142$. ------------ **Constraints and Notes** This problem uses **bundled tests**. - Subtask 1 (5 pts): $n\leq 6$. - Subtask 2 (15 pts): $n\leq 80$. - Subtask 3 (30 pts): $n\leq 800$. - Subtask 4 (50 pts): no special constraints. For $100\%$ of the testdata, it holds that: - $2\leq n \leq 10^6$. - $-10^9\leq x_i,y_i\leq 10^9$. - $1\leq v\leq 10^7$. - **All point coordinates are guaranteed to be pairwise distinct**. - **The given points are guaranteed to be able to reconstruct one and only one unique path.** ------------ $d(A,B)=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}$, where $A(x_A,y_A),B(x_B,y_B)$. ----- Source: [JROI-2 Summer Fun Round](https://www.luogu.com.cn/contest/30241) - T3 Idea&Sol&Data: [kkk's little simp](/user/104581) Std&Retest: [Tony2](/user/171288) Translated by ChatGPT 5