Cờ vua vô hạn

Xem PDF

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trên một bàn cờ vua có chiều dài và chiều rộng vô hạn, xuất hiện \(n\) con vua: \(K = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) \}\).

Nếu các bạn chưa biết chơi cờ, con vua mỗi bước có thể đi sang 8 ô kề nó, tính cả đi chéo.

Bạn có thêm một quân vua TỐI CAO đứng tại vị trí \((x, y)\), có sức mạnh của là tổng của từng số bước đi tối thiểu để con vua tối cao này có thể đi tới từng con vua khác.

Một cách quy củ, gọi \(d_i\) là số bước đi tối thiểu để vua tối cao có thể đi tới vua thứ \(i\), thì sức mạnh của vua tối cao là \(\sum_{i=1}^{n} d_i\).

\(n\) con vua trên không muốn vị tối cao này lộng hành, nên muốn sức mạnh của nó nhỏ nhất có thể. Bạn hãy tìm lượng sức mạnh tối thiểu này là bao nhiêu, và số lượng vị trí để đạt lượng tối thiểu này nhé.

Input

  • Dòng đầu tiên gồm số \(n\)
  • \(n\) dòng sau lần lượt gồm \(x_i, y_i\) là vị trí của con vua thứ \(i\).

Output

  • Gồm 2 số, là sức mạnh tối thiểu của con vua tối cao, và số vị trí đặt con vua này để đạt lượng sức mạnh tối thiểu.

Example

Test 1

Input
3
0 0
1 3
4 1
Output
5 1

Bình luận

Không có bình luận nào.