Original link: https://www.shuizilong.com/house/archives/bzoj-1185-hnoi2007%E6%9C%80%E5%B0%8F%E7%9F%A9%E5%BD%A2%E8%A6 %86%E7%9B%96/
Classic question. .
test template. .
#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]); pb = pa + pd()._1(); while (dott(pd(), P[r+1]-P[r])>0) r=suc(r),++rr; if (uu<rr)u=r,uu=rr; // # while (dett(pd(), P[u+1]-P[u])>0) u=suc(u),++uu; if (ll<uu)l=u,ll=uu; while (dott(pd(), P[l+1]-P[l])<0) l=suc(l),++ll; DB w = //dist(Line(P[r], P[r]+pd().lt()), Line(P[l], P[l]+pd().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] + pd()); 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)); }
This article is reproduced from: https://www.shuizilong.com/house/archives/bzoj-1185-hnoi2007%E6%9C%80%E5%B0%8F%E7%9F%A9%E5%BD%A2%E8%A6 %86%E7%9B%96/
This site is for inclusion only, and the copyright belongs to the original author.