Area Sums in Convex Polygons

 You are given a convex polygon 

P$P$ with N$N$ vertices. The vertices (in clockwise order) are v1,v2,…vN$v_1,v_2,\dots v_N$. The coordinates of vi$v_i$ are (xi,yi)$(x_i,y_i)$. All vertices have integer coordinates.

A diagonal of P$P$ is a line segment l$l$ joining two distinct vertices vi$v_i$ and vj$v_j$ of P$P$, such that l$l$ is not already an edge of P$P$. Every diagonal of P$P$ splits it into two smaller convex polygons, both having positive areas.

The evenness of a diagonal of P$P$ is the minimum of the areas of the two parts obtained when the polygon P$P$ is cut along this diagonal.

Let S$S$ be the sum of the evenness of all diagonals of P$P$.

Find the value of 2S(mod998244353)$2S(\mathrm{mod}998244353)$.

It can be shown that for all polygons P$P$ with integer coordinates, the value 2S$2S$ is an integer.

Input Format

• The first line of input contains an integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains an integer N$N$, the number of vertices of the convex polygon P$P$. This is followed by N$N$ lines describing the points of the convex polygon, in clockwise order.
• The ith$i^{th}$ subsequent line contains two space-separated integers, xi,yi$x_i,y_i$ — the coordinates of vi$v_i$.

Output Format

For each test case, print a new line with a single integer, the answer as per the problem statement.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 3≤N≤105$3\le N\le {10}^5$
• The sum of N$N$ over all test cases does not exceed 106${10}^6$
• The given polygon P$P$ is convex
• Every coordinate is an integer whose absolute value does not exceed 108${10}^8$

Subtasks

Subtask #1 ( 5 points): Sum of N$N$ over all test cases does not exceed 500$500$

Subtask #2 (15 points): Sum of N$N$ over all test cases does not exceed 2000$2000$

Subtask #3 (80 points): Original constraints

Sample Input 1 

4
4
-1 0
0 1
1 0
0 -1
4
-100000 0
0 100000
100000 0
0 -100000
3
0 0
0 1
1 0
5
-87260 82619
-59348 68595
86583 -16668
85637 -45559
-49307 -31316

Sample Output 1 

4
70225880
0
667956140

Explanation

Test case 1$1$: The given polygon is a square with side length 2–√$\sqrt{2}$. There are only two diagonals, both are identical and split the polygon equally into two halves each with area (2√)22=1$\frac{(\sqrt{2}{)}^2}{2}=1$. Thus S=min(1,1)+min(1,1)=2$S=\mathsf{m}\mathsf{i}\mathsf{n}(1,1)+\mathsf{m}\mathsf{i}\mathsf{n}(1,1)=2$. The value of 2S(mod998244353)$2S(\mathrm{mod}998244353)$ is thus 4$4$.

Test case 2$2$: The given polygon is identical to the previous case, except that all coordinates are multiplied by 105${10}^5$. Therefore the given sum gets multiplied by (105)2$({10}^5{)}^2$. Make sure you output the sum modulo 998244353$998244353$. Here 2S=4⋅1010$2S=4\cdot {10}^{10}$ and 4⋅1010(mod998244353)=70225880$4\cdot {10}^{10}(\mathrm{mod}998244353)=70225880$.

Test case 3$3$: There are no diagonals in this polygon, and so the answer is 0$0$.

• Tweet
• Share
• Share
• Share
• Share

Related Post