Corral the Cows 奶牛围栏

Corral the Cows 奶牛围栏

题目描述

Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral's edges must be parallel to the X,Y axes. FJ's land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral's borders. Help FJ by telling him the side length of the smallest square containing C clover fields.
约翰打算建一个围栏来圈养他的奶牛.作为最挑剔的兽类,奶牛们要求这个围栏必须是正方形的,而且围栏里至少要有C(1≤C≤500)个草场,来供应她们的午餐.
约翰的土地上共有N(C≤N≤500)个草场,每个草场在一块lxl的方格内,而且这个方格的坐标不会超过10000.有时候,会有多个草场在同一个方格内,那他们的坐标就会相同.
告诉约翰,最小的围栏的边长是多少?

输入格式

  • Line 1: Two space-separated integers: C and N
  • Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field. 第1行输入C和N,接下来N行每行输入一对整数,表示一个草场所在方格的坐标 # 输出格式
  • Line 1: A single line with a single integer that is length of one edge of the minimum size square that contains at least C clover fields. 输入最小边长.

样例输入

3 4
1 2
2 1
4 1
5 2

样例输出

4

OUTPUT DETAILS:

Below is one 4x4 solution (C&#39;s show most of the corral&#39;s area); many
others exist.

|CCCC
|CCCC
|*CCC*
|C*C*
+------

提示

Gold

信息

难度
10
分类
(无)
标签
递交数
4
已通过
0
通过率
0%
上传者