Trong kỳ thi chọn học sinh giỏi có ~N~ thí sinh tham gia, các thí sinh được đánh số từ ~1~ đến ~N~. Nhà thí sinh thứ ~i~ ở tại vị trí (~X_i~,~Y_i~) trong mặt phẳng ~xOy~. Nếu điểm thi ở vị trí ~(X,Y)~ thì khoảng cách di chuyển từ nhà thí sinh thứ i đến điểm thi được tính bằng |~X~-~X_i~ |+|~Y~-~Y_i~ |. Ban tổ chức muốn chọn đặt điểm thi tại một vị trí ~(X,Y)~ sao cho tổng khoảng cách di chuyển của tất cả các thí sinh là nhỏ nhất với ~X,Y~ là các số nguyên.
Yêu cầu: Hãy xác định vị trí có thể đặt điểm thi, nếu có nhiều vị trí thoả mãn thì chỉ ghi ra một vị trí bất kỳ trong các vị trí đó.
Dữ liệu vào có cấu trúc như sau:
- Dòng đầu ghi số nguyên dương ~N~;
- Dòng thứ ~i~ trong ~N~ dòng tiếp theo ghi hai số nguyên ~X_i~,~Y_i~ cách nhau một dấu cách.
Kết quả: Ghi ra hai số ~X~ và ~Y~ cách nhau một dấu cách.
Ví dụ:
INPUT
4
1 0
2 0
3 0
0 0
OUTPUT
1 0
Giải thích: Các vị trí ban tổ chức có thể chọn đặt điểm thi là: ~(1,0)~ hoặc ~(2,0)~, khi đó tổng khoảng cách di chuyển của các thí sinh là ~4~.
Ràng buộc:
- Có 20% số điểm tương ứng với ~2 ≤ N ≤ 1000~,0 ≤ ~X_i~ ≤ ~1000~ và ~Y_i~ = 0;
- Có 20% số điểm tương ứng với ~1000 ≤ N ~≤ ~10^5~,~0~ ≤ ~X_i ~≤ ~10^9~ và ~Y_i~ = 0;
- Có 20% số điểm tương ứng với ~2 ≤ N ≤ 100~ và ~0~ ≤ ~X_i~,~Y_i~ ≤ 100;
- Có 20% số điểm tương ứng với ~2 ≤ N ≤ 1000~ và ~0~ ≤ ~X_i~,~Y_i~ ≤ ~10^9~;
- Có 20% số điểm tương ứng với ~1000~ <~N~ ≤ ~10^5~ và ~0~ ≤ ~X_i~,~Y_i~≤ ~10^9~.
Comments
something went wrong