Marathon

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một cuộc chạy marathon gồm $N$ trạm kiểm soát phải đi qua theo thứ tự. Khoảng cách giữa hai điểm $(x_{1}, y_{1})$ và $(x_{2}, y_{2})$ là khoảng cách Manhattan: $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ .

Bạn được phép bỏ qua tối đa một trạm kiểm soát (trừ trạm đầu và trạm cuối) để giảm thiểu tổng quãng đường chạy.

Hãy tính tổng quãng đường ngắn nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$ .

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ và $y_{i}$ — tọa độ trạm thứ $i$ .

Dữ liệu ra

Một số nguyên duy nhất — tổng quãng đường ngắn nhất.

Ràng buộc

$3 \leq N \leq 100 000$
$- 1000 \leq x_{i}, y_{i} \leq 1000$

Ví dụ

Input	Output	Giải thích
4 0 0 8 3 11 -1 10 0	14	Bỏ trạm $(8, 3)$ : đi $(0, 0) \to (11, - 1) \to (10, 0)$ với tổng $12 + 2 = 14$ .

Bình luận

Không có bình luận tại thời điểm này.