Area Sums in Convex Polygons solution codechef
SOLUTION:- CLICK HERE
You are given a convex polygonwith vertices. The vertices (in clockwise order) are . The coordinates of are . All vertices have integer coordinates.
A diagonal ofis a line segment joining two distinct vertices and of , such that is not already an edge of . Every diagonal of splits it into two smaller convex polygons, both having positive areas.
The evenness of a diagonal ofis the minimum of the areas of the two parts obtained when the polygon is cut along this diagonal.
Letbe the sum of the evenness of all diagonals of .
Find the value of.
It can be shown that for all polygonswith integer coordinates, the value is an integer.
- The first line of input contains an integer , denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains an integer , the number of vertices of the convex polygon . This is followed by lines describing the points of the convex polygon, in clockwise order.
- The subsequent line contains two space-separated integers, — the coordinates of .
For each test case, print a new line with a single integer, the answer as per the problem statement.
- The sum of over all test cases does not exceed
- The given polygon is convex
- Every coordinate is an integer whose absolute value does not exceed
Subtask #1 ( 5 points): Sum ofover all test cases does not exceed
Subtask #2 (15 points): Sum ofover all test cases does not exceed
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
Test case: The given polygon is a square with side length . There are only two diagonals, both are identical and split the polygon equally into two halves each with area . Thus . The value of is thus .
Test case: The given polygon is identical to the previous case, except that all coordinates are multiplied by . Therefore the given sum gets multiplied by . Make sure you output the sum modulo . Here and .
Test case: There are no diagonals in this polygon, and so the answer is .