P3187 [HNOI2007]最小矩形覆盖

    • 375通过
    • 1.5K提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 凸包 旋转卡壳 枚举,暴力 2007 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一些点的坐标,要求求能够覆盖所有点的最小面积的矩形,输出所求矩形的面积和四个顶点坐标

    输入输出格式

    输入格式:

    第一行为一个整数n(3<=n<=50000),从第2至第n+1行每行有两个浮点数,表示一个顶点的x和y坐标,不用科学计数法

    输出格式:

    第一行为一个浮点数,表示所求矩形的面积(精确到小数点后5位),接下来4行每行表示一个顶点坐标,要求第一行为y坐标最小的顶点,其后按逆时针输出顶点坐标.如果用相同y坐标,先输出最小x坐标的顶点

    输入输出样例

    输入样例#1: 复制
    6 1.0 3.00000
    
    1 4.00000
    
    2.0000 1
    
    3 0.0000
    
    3.00000 6
    
    6.0 3.0
    输出样例#1: 复制
    18.00000
    
    3.00000 0.00000
    
    6.00000 3.00000
    
    3.00000 6.00000
    
    0.00000 3.00000

    说明

    感谢 @intruder 提供题目简述

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。