惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

U
Unit 42
博客园 - Franky
T
Tailwind CSS Blog
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
月光博客
月光博客
人人都是产品经理
人人都是产品经理
雷峰网
雷峰网
Hugging Face - Blog
Hugging Face - Blog
有赞技术团队
有赞技术团队
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
阮一峰的网络日志
阮一峰的网络日志
C
Check Point Blog
爱范儿
爱范儿
T
The Blog of Author Tim Ferriss
aimingoo的专栏
aimingoo的专栏
Stack Overflow Blog
Stack Overflow Blog
博客园 - 聂微东
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
L
LangChain Blog
云风的 BLOG
云风的 BLOG
MyScale Blog
MyScale Blog
Microsoft Security Blog
Microsoft Security Blog
The Cloudflare Blog
博客园 - 三生石上(FineUI控件)

某岛

AtCoder Beginner Contest 409 Luogu P5325. 【模板】Min_25 筛 UOJ #188. 【UR #13】Sanrd AtCoder Beginner Contest 371 AtCoder Beginner Contest 369 RPGMaker 2k3 百科 OneShot 的考古 2024“开创拓芯”游戏创享节的相关记录 CJ 回来后的戒断反应 Luogu P10221. [省选联考 2024] 重塑时光 Luogu P5308 [COCI2018-2019#4] Akvizna wqs 二分 歌唱王国 Lean 相关 BZOJ 3153. Sone1 The 2023 ICPC World Finals Luxor 新巴别塔 Sora 的想象与思考 Facebook Hacker Cup 2023 Round 1 AtCoder Beginner Contest 322 LLaMA 2 相关 HuggingFace AI Game Jam ACL 2023 Trans 相关… Luogu P2053. [SCOI2007] 修车 Luogu P1973. [NOI2011] NOI 嘉年华 Luogu P1933. [NOI2010] 旅行路线 Luogu P1954. [NOI2010] 航空管制 Luogu P2048. [NOI2010] 超级钢琴 Luogu P2046. [NOI2010] 海拔
BZOJ 1185. [HNOI2007]最小矩形覆盖
2022-08-27 · via 某岛

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: 日常