>>11 なんかかなりの難問に思えてきたな。 解法への足がかりが見えない。 凸包までは比較的簡単にたどり着いたけどそれからが闇の中。
凸包の重心が何か使えるだろうか？

最小包含円 という言葉もあるようだが、少なくとも 正方形の辺はこの円の直径以下。