C. VUONHOA - Vườn hoa

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

Đề bài

Trong mặt phẳng Oxy có n bông hoa, bông hoa thứ i ở tọa độ là (x_i;y_i) . Hãy tìm một tam giác vuông cân thỏa mãn:

  • Có các cạnh trùng với trục Ox và Oy;
  • Có thể bao toàn bộ n bông;
  • Diện tích nhỏ nhất.

Một bông hoa được coi là ở trong tam giác nếu nó nằm trong tam giác hoặc nằm trên cạnh của tam giác.

Dữ liệu vào:

  • Dòng đầu chứa số n\ (1≤n≤10^6) ;
  • n dòng tiếp theo, dòng thứ i gồm hai số nguyên x_i,y_i\ (1≤x_i;y_i≤10^9) là tọa độ của bông hoa thứ i .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là độ dài cạnh góc vuông của mảnh đất.

Ví dụ:

Dữ liệu vào:
6
1 1
2 3
3 1
1 2
1 3
2 2
Dữ liệu ra:
5	 
Giải thích: