#135. GCONVEX – Bao lồi của tập điểm

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Bao lồi của tập điểm trong mặt phẳng là tập lồi (đa giác lồi) nhỏ nhất (theo diện tích) chứa tất cả các điểm của tập đó.

Bài toán: Cho tập n điểm A_1, A_2, …, A_n . Hãy tìm bao lồi của tập điểm đó.

Dữ liệu vào:

  • Dòng đầu ghi số nguyên dương n ;
  • n dòng tiếp theo, dòng thứ i ghi hai số thực x_i, y_i là hoành độ và tung độ của điểm A_i .

Dữ liệu ra:

  • Gồm hai số m, S . Trong đó m là số đỉnh của bao lồi (số đỉnh của đa giác hoặc đoạn thẳng trong trường hợp suy biến) và S là diện tích bao lồi. Nếu có nhiều bao lồi thì chọn m là số đỉnh của bao lồi có ít đỉnh nhất.

Chú ý: Nếu diện tích không quá 10^6 thì làm tròn đến hàng phần trăm, ngược lại, làm tròn đến hàng đơn vị.

Ví dụ:

Dữ liệu vào:

8
2 3
2 2
4 1
6 3
5 6
4 3
2 3
2 4

Dữ liệu ra:

5 12.50

Giới hạn:

  • 3 ≤ n ≤ 10^5; |x_i|, |y_i| ≤ 10^6 .