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)~
Bình luận