Hull Edge Energy

Difficulty: 1800 6000 ms 128 MB

geometry

Build the convex hull and print the sum of the SQUARED lengths of its edges (an integer, avoiding floating point). A hull of fewer than 2 vertices has energy 0.

Input: the first line has N; the next N lines have distinct points x y.

Output: the sum of squared hull-edge lengths.

Constraints:

• 1 ≤ N ≤ 10⁵
• |coordinates| ≤ 10⁶

Sample Tests

4
0 0
3 0
3 4
0 4

50

2
0 0
1 1

4

Read the Editorial