#1264. QQ - Xếp hàng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập Đội Bắc Giang ôn thầy Đỗ Đức Đông - Tháng 10/2017

Để trình diễn một tiết mục trong màn khai mạc Đại hội thể thao quốc tế, đạo diễn X đã mời 𝑛 vận động viên tham gia. Theo kịch bản, 𝑛 vận động viên sẽ được xếp thành một hàng dọc hoặc một hàng ngang liên tiếp (song song với trục tọa độ). Hiện tại, vận động viên thứ 𝑖 đang ở vị trí (𝑥_𝑖, 𝑦_𝑖) , nếu vận động viên này di chuyển đến vị trí (𝑢_𝑖, 𝑣_𝑖) thì sẽ mất năng lượng là |𝑥_𝑖 − 𝑢_𝑖| + |𝑦_𝑖 − 𝑣_𝑖| .

Yêu cầu: Hãy giúp đạo diễn xác định cách xếp hàng để tổng năng lượng di chuyển của cả 𝑛 vận động viên là nhỏ nhất.

Dữ liệu vào:

  • Dòng đầu ghi hai số nguyên dương 𝑛 ;
  • Tiếp theo là 𝑛 dòng, dòng thứ 𝑖 chứa hai số nguyên 𝑥_𝑖, 𝑦_𝑖 , các số có giá trị tuyệt đối không vượt quá 10^9 .

Dữ liệu ra:

  • Ghi ra một dòng chứa một số nguyên là tổng năng lượng di chuyển của cả 𝑛 vận động viên.

Ví dụ:

Dữ liệu vào:
3
1 1
1 2
3 3
Dữ liệu ra:
2

Giới hạn:

  • Subtask \#1: 0 ≤ 𝑥_𝑖, 𝑦_𝑖 ≤ 10^2; 𝑛 ≤ 10^2 ;
  • Subtask \#2: 0 ≤ 𝑥_𝑖, 𝑦_𝑖 ≤ 10^4; 𝑛 ≤ 10^4 ;
  • Subtask \#3: 𝑛 ≤ 10^5 .