#1444. SQUARE - Tìm hình vuông

Cho điểm trên mặt phẳng với hệ tọa độ Đề-các vuông góc Ο𝑥𝑦. Các điểm được đánh số từ tới , điểm thứ có tọa độ . Ta nói một điểm được phủ bởi một hình vuông nếu điểm đó nằm ở miền trong của hình vuông hoặc nằm trên cạnh hình vuông.

Câu hỏi : Tìm số nguyên dương nhỏ nhất sao cho có thể đặt hai hình vuông có cạnh song song với trục tọa độ, kích thước để phủ hết tất cả điểm đã cho.

Câu hỏi : Tìm số nguyên dương nhỏ nhất sao cho có thể đặt hai hình vuông có cạnh song song với trục tọa độ, kích thước , không có điểm chung, để phủ hết tất cả điểm đã cho.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương là số bộ dữ liệu, nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một bộ dữ liệu:
  • Dòng đầu chứa số nguyên dương ;
  • dòng tiếp theo, dòng thứ chứa hai số nguyên .

Dữ liệu ra:

• Ứng với mỗi bộ dữ liệu vào, ghi ra hai số nguyên dương trên một dòng là đáp số cho hai câu hỏi tương ứng.

Ví dụ:

Dữ liệu vào:

1
7
1 1
4 2
6 3
1 4
3 5
5 5
6 6

Dữ liệu ra:

3 4