Minimum Sum of Squared Diameters after Chord Split

Given a convex polygon \(P\) with \(n\) vertices (listed in order either clockwise or anticlockwise), you need to choose two non-adjacent vertices such that the line (chord) connecting them splits \(P\) into two smaller polygons \(Q\) and \(R\), each having a positive area (i.e. at least 3 vertices).

Let \(d(Q)\) be the diameter (the maximum Euclidean distance between any two vertices) of polygon \(Q\) and \(d(R)\) be the diameter of polygon \(R\). The task is to determine the minimum possible value of \[ (d(Q))^2 + (d(R))^2 \] when choosing a valid chord.

Note: Distances are computed in Euclidean metric and all distance calculations are based on squared distances, to avoid precision issues with square roots.

inputFormat

The first line contains an integer \(n\) (\(4 \le n \le 200\), for instance) representing the number of vertices of the convex polygon. Each of the following \(n\) lines contains two space-separated numbers representing the \(x\) and \(y\) coordinates of a vertex. The vertices are given in order along the boundary of \(P\).

outputFormat

Output a single number, the minimum value of \((d(Q))^2 + (d(R))^2\) achievable by choosing an appropriate chord. If the result is an integer, you may output it without any decimal point.

sample

4
0 0
0 1
1 1
1 0

4