# 某島

… : "…アッカリ～ン . .. . " .. .
August 27, 2022

## BZOJ 1185. [HNOI2007]最小矩形覆蓋

#include <lastweapon/geometry>
using namespace lastweapon;
using namespace CG;

typedef vector<Po> VP;
/*#define suc(x) (x+1==n?0:x+1)
DB rc(const VP& P){
int n = SZ(P)-1, j = 1; DB d2 = 0; REP(i, n){
while (dett(P[i+1]-P[i], P[j+1]-P[j])>0) j=suc(j);
checkMax(d2, max(dist2(P[i], P[j]), dist2(P[i+1], P[j+1])));
}
return d2;
}*/

#define suc(x) (x+1==n?0:x+1)
DB rc(const VP& P){
VP R;
int n=SZ(P)-1,l=1,r=1,u=1,ll=1,rr=1,uu=1; DB z=OO; REP(i, n){

Line p(P[i], P[i+1]); p.b = p.a + p.d()._1();

while (dott(p.d(), P[r+1]-P[r])>0) r=suc(r),++rr; if (uu<rr)u=r,uu=rr; //#
while (dett(p.d(), P[u+1]-P[u])>0) u=suc(u),++uu; if (ll<uu)l=u,ll=uu;
while (dott(p.d(), P[l+1]-P[l])<0) l=suc(l),++ll;

DB w = //dist(Line(P[r], P[r]+p.d().lt()), Line(P[l], P[l]+p.d().lt())); //?
dot(p, P[r]) - dot(p, P[l]);
DB h = dist(p, P[u]);
//cout << w << " " << h << endl;
if (checkMin(z, w*h)) {
R.clear();
R.PB(P[l]&p); R.PB(P[r]&p);
p = Line(P[u], P[u] + p.d());
R.PB(P[l]&p); R.PB(P[r]&p);
}
}

printf("%.5f\n", z+EPS);
R = getCH(R); int o = 0; REP(i, 4) {
if (sgn(R[i].y, R[o].y) < 0 || sgn(R[i].y, R[o].y) == 0 &&sgn(R[i].x, R[o].x) < 0) o = i;
R.PB(R[i]);
}

REP(i, 4) printf("%.5f %.5f\n", R[o+i].x+EPS, R[o+i].y+EPS);
}

VP P; int n;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

RD(n); P.resize(n); REP(i, n) P[i].in();
rc(getCH(P));
}