POINT - Khoảng cách mong manh
Giới hạn- Thời gian: 0.43s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: hard7771988
- Nguồn bài: Dựa theo 1 bài dễ hơn của USACO