Nguồn: Free Contest

Xét một tứ giác đơn ~ABCD~ bất kì có đường chéo ~AC~. Đường thẳng ~AC~ sẽ chia mặt phẳng Oxy thành hai nửa mặt phẳng: một nửa mặt phẳng "dương" (nửa mặt phẳng nằm bên trái nếu nhìn theo chiều ~AC~) và một nửa mặt phẳng "âm" (nửa mặt phẳng nằm bên phải nếu nhìn theo chiều ~AC~). Ta nhận xét rằng, ~B~ và ~D~ phải nằm ở hai nửa mặt phằng khác nhau và đồng thời:

\(S_{ABCD} = S_{∆ABC} + S_{∆ADC} = AC \times d(B, AC) + AC \times d(D, AC)\)

Với kí hiệu ~d(P, AC)~ là khoảng cách từ điểm ~P~ đến đường thẳng ~AC~. Do đó, để diện tích tứ giác ~ABCD~ là lớn nhất có thể, khoảng cách từ ~B~ và ~D~ đến đường thẳng ~AC~ cũng phải lớn nhất có thể.

Từ đó, ý tưởng để giải bài toán này như sau: Duyệt qua tất cả các đường chéo có thể của tứ giác cần tìm (mỗi đường chéo sẽ là một cặp điểm trong ~N~ điểm đã cho):

• Nếu một trong hai nửa mặt phẳng tạo bởi đường chéo đang xét không chứa điểm nào, ta sẽ bỏ qua cặp điểm này.
• Ngược lại, với mỗi nửa mặt phẳng ta cần tìm điểm có khoảng cách lớn nhất đến đường chéo đang xét, và lấy ~2~ điểm đó làm hai điểm còn lại của tứ giác. Cuối cùng, ta tính diện tích của tứ giác tạo thành rồi cập nhật đáp án.

Độ phức tạp: ~O(N^3)~