Skip to content

11522: 【原1522】cwx收集苹果

题目

题目描述

author: bywbilly, HNOI 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1522

Description

cwx和某人在野外郊游,忽然发现地上散落着一堆苹果,某人是个吃货,就说cwx你去帮我把苹果都收集起来吧。

因为种种限制,cwx只能收集3次,每次可以收集一块L * L的正方形内的所有苹果。当然,L越大收集时间越长,这当然是cwx和某人不愿意看到的。

我们不妨将野外建立一个平面直角坐标系,设第i个苹果的坐标为(Xi,Yi),3个L*L的正方形的边要求平行与坐标轴,一个苹果如果在正方形的边界上,也算作被收集。

Input Format

输入共有两行。

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

30%的数据:N <= 200

50%的数据:N <= 2000

100%的数据:N <= 20000

Output Format

输出最小的L。

Sample Input

4
0 1
0 -1
1 0
-1 0

Sample Output

1

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!