   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Diamonds
 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 378 Accepted: 82

Description

Consider a planer grid of M rows and N columns. This grid has exactly MN intersections, each of which is denoted by a pair of coordinates (i, j) where i = 0, 1, ..., N-1 and j = 0, 1, ..., M-1.

Suppose K <= MN points are now placed on K distinct grid intersections.

Consider a diamond shaped area D(i, j, r) such that the centre of the area is at intersection (i, j) and the shape itself is a square of diagonal length 2r, rotated 45 degree clockwise, where i = 0, 1, ..., N-1, j = 0, 1, ..., M-1, and r, the radius of the diamond shape, is any integer greater than 0.

Manoranjan is interested in finding the minimum radius, Rmin(Pmin), of such a diamond shape that would guarantee of covering at least Pmin points no matter at which grid intersection the centre of the shape resides, where Pmin = 1, 2, ..., K. Let Pmax(Pmin) be the maximum number of points that can be covered by a diamond shape of radius Rmin(Pmin). Consider the example in the figure below. Five points at intersections (0,0), (4,0), (2,2), (0,4), and (4,4) are placed on a planer grid of 5 rows and 7 columns. The diamond shape D(2,4,1) covers none of the points, D(2,1,2) covers one point, and D(3,3,4) covers four points. Input

The number of rows, M, and columns, N, of the grid are given in line 1. K number of points are then given in the next one or more lines, where K <= MN. You may assume that 1 <= M <= 100 and 1 <= N <= 100. A pair of integers, representing x- and y-coordinates of the point respectively, denotes each point.

All the values given in any of the input lines are separated from each other by one or more white spaces including tabs.

Output

Any given point outside the grid is discarded as "invalid" entries, e.g., the last point given in the sample input is discarded. For each possible Pmin value, corresponding Rmin(Pmin) and Pmax(Pmin) values are written in a separate line as per the format shown in the sample output. However, a line of output should only be generated if a diamond shape of radius Rmin(Pmin) guarantees to cover exactly Pmin points. In the sample output, no line is generated for Pmin = 2 as Rmin(2) = Rmin(3) = 6.

All values are written right aligned to their column headings.

Sample Input

```5 	7
0 	0 0 	4
4 0
4 4	       2 2
0 5```

Sample Output

```Pmin  Rmin(Pmin)  Pmax(Pmin)
1           4           5
3           6           5
4           8           5
5          10           5```

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top