>>108 この凸包図を眺めてると、正解の正方形は 左辺の一番長い線を1辺とした正方形になりそうだが、それをどうやって求めるのか。

How to find the minimum-area-rectangle (MAR) fitted on the given points?
https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points

最初に書いた人は、凸包を求めて重心を中心として1度ずつ回転させるやり方を考えたらしいが、下の方で良い解法のコメントが付いてた。

https://i.stack.imgur.com/ExZl3.png

少しずつ回転させるのではなくて、長方形の1辺は必ず凸包の辺のどれかと重なってるはずだから、凸包の辺の角度だけをとって試せば良いとのこと。
これなら重心を求める必要もないし、時間はかからない。

長方形が求まったら、座標系の中に入る正方形にすれば良いがはみ出してたら、参考解かな。

このアルゴリズムは、
The algorithm you are looking for is known in polygon generalisation as "smallest surrounding rectangle".
凸包最小長方形の解法とでも言えば良いのかな。