以下は試作実験programと結果
①凸包の辺の角度にのみ傾ける(それ以外の角度は略)　②長方形⇒正方形補正は略 ③頂点座標が0～999の範囲外も出力
use List::Util qw{min max}; use Math::Trig;
@X = qw{94 110 787 850 472 388}; @Y = qw{31 927 897 598 199 157};
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max @x); @y = (min(@y), max @y);
　$w = max($x[1] - $x[0], $y[1] - $y[0]);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0,1,0,1;
　@y = map{sp @f, $x[$_], $y[$_]} 0,0,1,1;
　#next if min@x<0 or 999<max@x or min@y<0 or 999<max@y;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,th,$th,X,[@x],Y,[@y],w,$w} } }
@t = sort{$$a{w}<=>$$b{w}} @t;
do {@x = @{$_->{X}}; @y = @{$_->{Y}};
　printf"%d: (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f), (%7.3f,%7.3f): w=%7.3f, th=%7.3f°\n",
　　++$k,$x[0],$y[0],$x[1],$y[1],$x[2],$y[2],$x[3],$y[3],$$_{w},rad2deg $$_{th}} for @t[0..4];

1: (752.170,710.324), ( 94.000,710.324), (752.170, -8.662), ( 94.000, -8.662): w=873.451, th=168.102°
2: ( 70.342, 31.983), (863.100, 31.983), ( 70.342,891.839), (863.100,891.839): w=895.830, th= 2.537°
3: ( 94.000, 30.990), (855.637, 30.990), ( 94.000,913.391), (855.637,913.391): w=896.143, th= 1.023°
4: (699.348,547.478), ( 94.000,547.478), (699.348,-34.520), ( 94.000,-34.520): w=945.899, th=160.148°
5: ( 94.000, 29.184), (671.086, 29.184), ( 94.000,1007.681), (671.086,1007.681): w=978.102, th=-23.199°
真の極小解は中途半端な角度にあるのか…