Có n thành phố trên mặt phẳng. Thành phố i nằm tại tọa độ nguyên (xi,yi); nhiều thành phố có thể nằm cùng một tọa độ.
Bạn có thể xây một con đường giữa hai thành phố i và j với chi phí
min(∣xi−xj∣,∣yi−yj∣).
Hãy xây một số con đường sao cho có thể đi lại giữa mọi cặp thành phố, đồng thời tổng chi phí là nhỏ nhất.
Input
Dòng đầu chứa số nguyên n.
Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên xi,yi.
Output
In một số nguyên - tổng chi phí nhỏ nhất để nối toàn bộ thành phố.
Constraints
2≤n≤105.
0≤xi,yi≤109.
Tọa độ của các thành phố không nhất thiết khác nhau.
Scoring
Subtask 1 (50% số điểm): n≤8.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
5
0 0
5 2
6 10
12 9
20 3
Output
5
Giải thích: Có thể nối 2-3, 3-4, 2-5 với chi phí 1 cho mỗi đường và nối 1-2 với chi phí 2. Tổng chi phí là 1+1+1+2=5.
Lời giải tóm tắt
Ý tưởng: Không thể sinh đủ O(n^2) cạnh của đồ thị đầy đủ. Ta chỉ cần hai nhóm cạnh ứng viên: giữa hai thành phố liên tiếp khi sắp theo x, và giữa hai thành phố liên tiếp khi sắp theo y.
Ý tưởng: Xét một lát cắt bất kỳ và một cạnh nhẹ nhất (u,v) cắt qua lát đó. Nếu trọng số của cạnh được quyết định bởi chênh lệch x, trên đoạn thứ tự theo x từ u tới v phải có một cặp liên tiếp nằm ở hai phía lát cắt; chênh x của cặp này không lớn hơn chênh x của (u,v), nên trọng số của nó cũng không lớn hơn. Trường hợp chênh y tương tự. Vì vậy tập cạnh ứng viên chứa một cạnh nhẹ nhất cho mọi lát cắt và chứa ít nhất một MST.
Ý tưởng: Tạo tối đa 2(n-1) cạnh như trên rồi chạy Kruskal.
Ý tưởng: Độ phức tạp là O(n log n) thời gian và O(n) bộ nhớ.
Ý tưởng: Bốn cạnh được nêu trong giải thích mẫu nối đủ năm thành phố với tổng chi phí 5.