Area Sums in Convex Polygons solution codechef

 

SOLUTION:- CLICK HERE

 

You are given a convex polygon PP with NN vertices. The vertices (in clockwise order) are v1,v2,…vNv1,v2,…vN. The coordinates of vivi are (xi,yi)(xi,yi). All vertices have integer coordinates.

A diagonal of PP is a line segment ll joining two distinct vertices vivi and vjvj of PP, such that ll is not already an edge of PP. Every diagonal of PP splits it into two smaller convex polygons, both having positive areas.

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

Let SS be the sum of the evenness of all diagonals of PP.

Find the value of 2S(mod998244353)2S(mod998244353).

It can be shown that for all polygons PP with integer coordinates, the value 2S2S is an integer.

Input Format

• The first line of input contains an integer TT, denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains an integer NN, the number of vertices of the convex polygon PP. This is followed by NN lines describing the points of the convex polygon, in clockwise order.
• The ithith subsequent line contains two space-separated integers, xi,yixi,yi — the coordinates of vivi.

Output Format

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

Constraints

• 1≤T≤1051≤T≤105
• 3≤N≤1053≤N≤105
• The sum of NN over all test cases does not exceed 106106
• The given polygon PP is convex
• Every coordinate is an integer whose absolute value does not exceed 108108

Subtasks

Subtask #1 ( 5 points): Sum of NN over all test cases does not exceed 500500

Subtask #2 (15 points): Sum of NN over all test cases does not exceed 20002000

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 11: The given polygon is a square with side length 2–√2. There are only two diagonals, both are identical and split the polygon equally into two halves each with area (2√)22=1(2)22=1. Thus S=min(1,1)+min(1,1)=2S=min(1,1)+min(1,1)=2. The value of 2S(mod998244353)2S(mod998244353) is thus 44.

Test case 22: The given polygon is identical to the previous case, except that all coordinates are multiplied by 105105. Therefore the given sum gets multiplied by (105)2(105)2. Make sure you output the sum modulo 998244353998244353. Here 2S=4⋅10102S=4⋅1010 and 4⋅1010(mod998244353)=702258804⋅1010(mod998244353)=70225880.

Test case 33: There are no diagonals in this polygon, and so the answer is 00.

SOLUTION:- CLICK HERE