Submit solution
Points:
400.00 (partial)
Time limit:
2.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Trên mặt phẳng với hệ trục tọa độ Descartes vuông góc Ο𝑥𝑦 cho 𝑛 điểm đánh số từ 1 tới 𝑛, có thể có những điểm trùng nhau nhưng có ít nhất 3 điểm không thẳng hàng. Điểm thứ 𝑖 có tọa độ (~𝑥_𝑖~, ~𝑦_𝑖~ ). Hãy tìm một đa giác lồi với diện tích nhỏ nhất mà miền giới hạn bởi đa giác (tính cả đường biên) chứa tất cả 𝑛 điểm đã cho. (Đa giác lồi được định nghĩa là miền giới hạn bởi một đường gấp khúc khép kín không tự cắt có các đỉnh phân biệt và các góc nhỏ hơn 180 độ).
Dữ liệu vào:
- Dòng 1 chứa số nguyên dương 𝑛 (3 ≤ 𝑛 ≤ ~10^5~)
- 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa hai số nguyên ~𝑥_𝑖~, ~𝑦_𝑖~ có giá trị tuyệt đối không quá ~10^9~
Kết quả:
- Dòng 1 ghi số đỉnh (𝑚) của đa giác tìm được
- Dòng 2 ghi diện tích đa giác tìm được với đúng 1 chữ số sau dấu chấm thập phân.
- 𝑚 dòng tiếp theo, dòng thứ 𝑗 ghi tọa độ đỉnh thứ 𝑗 của đa giác tìm được theo thứ tự sau: Đỉnh trái nhất trongsố những đỉnh thấp nhất của bao lồi được đánh số 1, các đỉnh còn lại được đánh số theo thứ tự tạo thành đa giác liệt kê theo chiều ngược với chiều kim đồng hồ.
Các số trên một dòng của input/output files được/phải ghi cách nhau ít nhất một dấu cách.
Ví dụ:
INPUT
11
-1 4
-4 2
-5 0
0 0
-3 -2
1 -2
5 -2
2 -3
-1 -4
1 -4
3 -4
OUTPUT
6
46.0
-1 -4
3 -4
5 -2
-1 4
-4 2
-5 0
![](http://oj.lequydon.net/media/martor/068bf330-79b4-4d8b-8bd9-1bd3aaa2970b.png)
Comments