2

BZOJ 1185. [HNOI2007]最小矩形覆盖

 2 years ago
source 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/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
August 27, 2022

经典题。。
测模板。。

#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));
}

Posted by xiaodao
Category: 日常


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK