P2218 [HAOI2007]覆盖问题

    • 151通过
    • 460提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 二分答案 深度优先搜索,DFS 贪心 各省省选 2007 河南 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某人在山上种了N棵小树苗。冬天来了,温度急速下降,小树苗脆弱得不堪一击,于是树主人想用一些塑料薄膜把这些小树遮盖起来,经过一番长久的思考,他决定 用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系,设第i棵小树的坐标为(Xi,Yi),3个L*L的正方形的边要求平行 与坐标轴,一个点如果在正方形的边界上,也算作被覆盖。当然,我们希望塑料薄膜面积越小越好,即求L最小值。

    输入输出格式

    输入格式:

    第一行有一个正整数N,表示有多少棵树。

    接下来有N行,第i+1行有2个整数Xi,Yi,表示第i棵树的坐标,保证不会有2个树的坐标相同。

    输出格式:

    一行,输出最小的L值。

    输入输出样例

    输入样例#1: 复制
    4
    0 1
    0 -1
    1 0
    -1 0
    
    输出样例#1: 复制
    1

    说明

    数据范围

    100%的数据,-1,000,000,000<=Xi,Yi<=1,000,000,000

    30%的数据,N<=100

    50%的数据,N<=2000

    100%的数据,N<=20000

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