CAO TỐC

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, Swift
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(N\) điểm dân cư. Điểm thứ \(i\) có toạ độ \(x_i\), \(y_i\). Người ta muốn xây dựng một đường cao tốc song
song với trục hoành. Khi đó, từ mỗi điểm dân cư nhân dân sẽ làm một đường dân sinh từ làng mình đến
đường cao tốc theo hướng song song với trục tung. Mỗi làng làm một đường (không chung nhau). Hỏi
rằng tổng độ dài các đường dân sinh nhỏ nhất là bao nhiêu (hai đường dân sinh có thể trùng nhau trên
mặt phẳng toạ độ - khi đó tất nhiên có một cái ở bên trên).

Input

  • Dòng thứ nhất chứa số nguyên dương \(N\) \((0 < N \leq 10^6)\)
  • \(N\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(x_i\), \(y_i\) \((|x_i|, |y_i| \leq 10^6)\) thể hiện toạ độ của một điểm.

Output

  • Ghi ra một số duy nhất là đáp số tìm được.

Example

Test 1

Input
5
1 3
4 5
2 -1
5 -5
3 -3
Output
16

Bình luận

Không có bình luận nào.