TopCoder Statistics - Problem Statement

Problem Statement

This problem has a non-standard time limit of 10 seconds.

Let P be a (strictly) convex polygon, let V be the set of vertices of P, and let W be any subset of V of size 3 or more. Then, the convex hull of W is called a subpolygon of P.

For instance, let (0,0), (2,0), (3,3), (0,2) be the vertices of a convex polygon P. This polygon has five subpolygons: the polygon itself and four triangles.

You are given a special convex polygon P on 4n vertices, all having integer coordinates. Calculate the sum of areas of all subpolygons of P. Express the answer as a fraction A/B, where gcd(A,B) = 1. Let B^-1 be the multiplicative inverse of B modulo 998244353. Return A*B^-1 modulo 998244353.

The procedure for generating the input polygon P is as follows. You are given an int n. Consider the square with vertices (n,0), (0,n), (-n,0), (0,-n). On the boundary of this square there are exactly 4n points with integer coordinates. (This includes all four corners of the square.) Start at an arbitrary one of these 4n points and label them T[0] through T[4n-1] in counter-clockwise order.

Let P[0] be an arbitrary point in the plane. For all i from 1 to 4n, set P[i] = P[i-1] + T[i-1]. I.e., if P[i-1] has coordinates (x1,y1) and T[i-1] has coordinates (x2,y2), the new point P[i] has coordinates (x1+x2,y1+y2).

The polygon P you should process is the polygon with vertices at P[0], P[1], ..., P[4n-1]. Note that P is always a simple convex polygon, and that the answer you should return does not depend on the choices you made during the construction. Also note that the above process sets P[4n] to the same point as P[0].

Definition

Class:: Subpolygon
Method:: sumOfAreas
Parameters:: int
Returns:: int
Method signature:: int sumOfAreas(int n)
(be sure your method is public)

Constraints

n will be between 1 and 125,000, inclusive.

Examples

1

Returns: 3

One possible polygon P is {(0,0),(1,0),(0,1),(1,1)}. It has five subpolygons: P itself has area 1, and each of the four triangles has area 1/2. The sum of these areas is 3.
2

Returns: 1650

For n = 2 we may choose that T = {(2,0), (1,1), (0,2), (-1,1), (-2,0), (-1,-1), (0,-2), (1,-1)} and that P[0] = (0,0). These two choices will then produce the polygon P = {(0,0), (2,0), (3,1), (3,3), (2,4), (0,4), (-1,3), (-1,1)}. This polygon P has 219 subpolygons. All these sub-polygons happen to have integral areas. The number of sub-polygons with area 1, 2, 3, ..., 14 is {8, 8, 20, 12, 8, 34, 16, 14, 28, 22, 20, 20, 8, 1}.
35

Returns: 132946800

Do not forget to calculate the result modulo 998244353.
124999

Returns: 483134074
125000

Returns: 977938101
3

Returns: 184527
4

Returns: 10879320
5

Returns: 461374023
6

Returns: 92275762
7

Returns: 763365104
8

Returns: 687857166
9

Returns: 754629825
10

Returns: 452624163
47

Returns: 701128126
69

Returns: 109996738
135

Returns: 87107455
792

Returns: 550636463
4023

Returns: 141817167
12306

Returns: 847664327
118293

Returns: 853615835
100001

Returns: 421818861
102343

Returns: 973189880
89232

Returns: 413306507
16383

Returns: 286812279
16384

Returns: 221046812
16385

Returns: 259711468
32767

Returns: 735166269
32768

Returns: 101030739
32769

Returns: 198742540
65535

Returns: 344999661
65536

Returns: 387004040
65537

Returns: 452079417
65538

Returns: 447636276
65539

Returns: 863714471
65534

Returns: 265308248
65533

Returns: 737340991
65532

Returns: 793754674
65540

Returns: 335609374
65541

Returns: 674724179
65542

Returns: 149328308
119320

Returns: 496234584
118432

Returns: 195431473

Statistics

Problem Statement for "Subpolygon"

Problem Statement

Definition

Constraints

Examples