Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

POINT - Khoảng cách mong manh

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/point


Cho N điểm phân biệt trên mặt phẳng toạ độ . Toạ độ của điểm i là ( Xi , Yi ) trong đó Xi , Yi là các số nguyên ( -10000 ≤ Xi , Yi ≤ 10000 ) .
Ta định nghĩa khoảng cách giữa 2 điểm (X1,Y1) , (X2,Y2) là khoảng cách Manhattan được tính = | X1 – X2 | + | Y1 – Y2 | .
Hàm Q(X,Y) := | X – X1 | + | X – X2 | + … + | X – Xn | + | Y – Y1 | + … |Y – Yn | .
( Trong đó X , Y là 2 số nguyên thoả mãn -10000 ≤ X , Y ≤ 10000 và Xi ≠ X hoặc Yi ≠ Y với mọi i = 1 .. n ) .
Hãy tìm tập tất cả các điểm nguyên (X,Y) để hàm Q(X,Y) có giá trị nhỏ nhất .

Input

Dòng 1 : số nguyên dương T là số bộ test ( T ≤ 20 ) .
Các nhóm dòng sau mô tả 1 bộ test . 1 bộ test sẽ có format như sau :
Dòng 1 : số nguyên dương N ( N ≤ 10000 ) .
N dòng tiếp theo , dòng thứ i gồm 2 số nguyên là toạ độ của điểm thứ i .

Output

Với mỗi bộ test ghi 1 dòng gồm 2 số nguyên dương S , K tương ứng là giá trị nhỏ nhất của hàm Q(X,Y) và số lượng điểm thoả mãn yêu cầu .

Example

Input:
1
2
0 1
1 0

Output:
2 2

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-03-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Dựa theo 1 bài dễ hơn của USACO

hide comments
2017-06-28 16:58:11
Test yếu, không bắt được hết lỗi
2015-10-30 08:38:33
Binary search O(nlog(n)log(1e9))

Last edit: 2015-10-30 08:40:26
2012-03-31 03:30:13 trandatbav
Cac bác xem giúp em chứ em làm có n log n mà tle được à :((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.