CONVEXHULL - Bao lồi
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Trên mặt phẳng với hệ trục tọa độ Descartes vuông góc Oxy cho điểm đánh số từ 1 tới n, 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 độ (xi,yi). 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ả n đ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: 

- Dòng 1 chứa số nguyên dương n (3<=n<=105).
​- n dòng tiếp theo, dòng thứ chứa hai số nguyên xi,yi có giá trị tuyệt đối không quá  109

Kết quả: 

- Dòng 1 ghi số đỉnh (m) 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ứ j ghi tọa độ đỉnh thứ của đa giác tìm được theo thứ tự sau: Đỉnh trái nhất trong số 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ồ.

Ví dụ

Input

11
-5 0
-4 2
-3 -2
-1 4
-1 -4
0 0
1 -2
1 -4
2 -3
3 -4
5 -2

Output

6
46.0
-1 -4
3 -4
5 -2
-1 4
-4 2
-5 0


Nguồn: NTH 20162017

Back to Top