Khoảng cách mong manh

View as PDF

Submit solution

Points: 1.07 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Dựa theo 1 bài dễ hơn của USACO
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~N~ điểm phân biệt trên mặt phẳng toạ độ. Toạ độ của điểm ~i~ là ~(X_i~, ~Y_i)~ trong đó ~X_i~, ~Y_i~ là các số nguyên ~(- 10000 \leq X_i~, ~Y_i \leq 10000)~.

Ta định nghĩa khoảng cách giữa ~2~ điểm ~(X_1, Y_1)~, ~(X_2, Y_2)~ là khoảng cách Manhattan được tính ~=|X_1 - X_2| + |Y_1 -Y_2|~.

Hàm ~Q(X, Y) = |X - X_1|+|X - X_2|+\dots +|X - X_n | + |Y - Y_1|+ \dots |Y -Y_n|~.

(Trong đó ~X~, ~Y~ là ~2~ số nguyên thoả mãn ~- 10000 \leq X~, ~Y \leq 10000~ và ~X_i \neq X~ hoặc ~Y_i \neq 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 \leq 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 \leq 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.

Sample Input

1
2
0 1
1 0

Sample Output

2 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.