http://ntucoder.net/Problem/Details/5659
Cho n điểm với tọa độ nguyên trên một mặt phẳng . Các điểm đã cho thỏa mãn điều kiện là : 3 điểm bất kì trong n điểm trên tạo thành một tam giác có diện tích không vượt quá S .
Tam giác đẹp là tam giác chứa tất cả n điểm trên .
Yêu cầu : Hãy chỉ ra một tam giác đẹp mà diện tích của tam giác đó không vượt quá 4 x S .
Đưa ra tọa độ của 3 điểm tam giác đó .
INPUT :
Dòng đầu gồm 2 số nguyên dương n , S ( 3 < n < 5000 , 1 < S < 1018 ) .
n dòng sau mỗi dòng gồm 2 số xi , yi ( -108 < xi , yi < 108 ) .
OUTPUT :
Đưa ra tọa độ của 3 điểm tam giác đó .
Ví dụ
- input
4 1
0 0
1 0
0 1
1 1
- output
-1 0
2 0
0 2
Bài này em có ý tưởng như sau:
Do số điểm là hữu hạn nên số tam giác tạo ra hữu hạn
Giả sử
S_{MNP} \leq S lớn nhất
qua M,N,P kể các đường song song với cạnh đối diện chúng cắt nhau tại ABC khi đó
S_{ABC}≤4S_{MNP}≤4
Giả sử có điểm D ở ngoài tam giác ABC khi đó S_{MNP}<S_{DMN} (vô lí)
Tam giác ABC (gọi là anti-median của MNP) thỏa mãn.
Sau đó, em sẽ dùng bao lồi để tìm tam giác diện tích lớn nhất. Ý tưởng của em như vậy có ổn không ạ? Vì vẫn có test em sai.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?