Subtask 1

Ta sẽ for lồng để tính tất cả các khoảng cách và sắp xếp giảm dần chúng, in ra phần tử thứ hai.

Độ phức tạp: \(O(N^2 log N)\).

Subtask 2

Ta sẽ tận dụng tính chất của khoảng cách và tìm ra các giá trị sau:

• Khoảng cách lớn nhất giữa các tọa độ \(x\) của hai ngôi nhà.
• Khoảng cách lớn nhất giữa các tọa độ \(y\) của hai ngôi nhà.
• Khoảng cách lớn thứ hai giữa các tọa độ \(x\) của hai ngôi nhà.
• Khoảng cách lớn thứ hai giữa các tọa độ \(y\) của hai ngôi nhà.

Ta có thể dễ dàng tìm được hai giá trị đầu tiên, còn khoảng cách lớn thứ hai trong các tọa độ \(x\) có thể là một trong hai giá trị sau:

• Độ dài tọa độ \(x\) lớn thứ hai trừ đi tọa độ \(x\) nhỏ nhất.
• Độ dài tọa độ \(x\) lớn nhất trừ đi tọa độ \(x\) nhỏ thứ hai.

Ta có thể tìm khoảng cách lớn thứ hai hai trong các tọa độ y một cách tương tự.

Có trường hợp nếu cùng một cặp ngôi nhà xuất hiện hai lần trong số đó, thì ta có thể sẽ bị sai.

Để giải quyết vấn đề này này ta sẽ liệt kê tất cả các ngôi nhà xuất hiện trong bốn cặp trên và tính khoảng cách giữa từng cặp ngôi nhà trong danh sách. Vì danh sách này sẽ chứa tối đa \(8\) ngôi nhà.

Độ phức tạp của thuật này là \(O(N)\)