408522: GYM103181 C Girth

Your friend, Ron, is a very gifted student, but he has one problem: he almost finishes high-school and has yet to publish his first paper. How tragic! Being under the pressure of his limited time, he decided to invent a new concept called the $$$Girth$$$ of a set of at least $$$3$$$ points in the euclidean plane, no $$$3$$$ of which are collinear.

The $$$Girth$$$ of a set of points is calculated in the following way:

• You compute the Convex Hull of the set of points.
• You sum up the squares of lengths of all segments forming the convex hull.

Now, as a last effort to see if this new concept is revolutionary, he asks for you help. Now, he gives you a set $$$S$$$ of distinct points in the euclidean plane, no $$$3$$$ of which are collinear. He would like you to calculate $$$\sum Girth(S')$$$, where $$$S' \subseteq S$$$ and $$$|S'| \geq 3$$$, i.e. he wants you to sum up the $$$Girth$$$ over all subsets of at least $$$3$$$ points of the initial set.

The first line of the input contains a single integer: $$$N$$$ ($$$3 \leq N \leq 1000$$$), the number of points in the set.

The next $$$N$$$ lines will contain $$$2$$$ integers: $$$X_i$$$ ($$$-10^9 \leq X_i \leq 10^9$$$) and $$$Y_i$$$ ($$$-10^9 \leq Y_i \leq 10^9$$$), the coordinates of each point.

It is guaranteed that all points are pairwise distinct and that there are no $$$3$$$ collinear points.

The output should contain one integer, representing the sum of the $$$Girth$$$ of each subsets of at least 3 points, modulo $$$998244353$$$.

6
1 1
0 2
-3 2
-4 1
-2 0
0 -3

2068

4
0 0
0 1
1 1
1 0

20