Gậy thần
Đề bài
Mô tả
Phép thuật từng được mọi dân tộc cổ xưa chấp nhận như một kỹ thuật để buộc các thế lực thần thánh phải giúp đỡ. Trong một câu chuyện nổi tiếng, một nhóm phù thủy ném gậy chống xuống sàn, những cây gậy biến thành rắn sống như có phép màu. Để đáp trả, một người khác ném cây gậy của mình xuống sàn, nó biến thành một con rắn rồi nuốt chửng những con rắn của nhóm phù thủy!
Phép màu duy nhất cần có trong bài này là lời giải của nó. Bạn được cho một cây gậy thần gồm nhiều đoạn thẳng, giữa các đoạn có khớp nối cho phép gập cây gậy lại. Tùy theo độ dài các đoạn và cách gập, các đoạn của cây gậy có thể được sắp xếp để tạo thành một số đa giác. Hãy xác định diện tích lớn nhất có thể được bao bởi các đa giác tạo thành khi gập cây gậy, mỗi đoạn thuộc về nhiều nhất một đa giác. Các đoạn chỉ được chạm nhau tại các đầu mút. Ví dụ, cây gậy ở hình bên trái dưới đây có năm đoạn và bốn khớp nối. Có thể gập nó để tạo thành một đa giác như hình bên phải.

Dữ liệu vào
Dữ liệu gồm nhiều bộ test, mỗi bộ test mô tả một cây gậy thần. Dòng đầu tiên của mỗi bộ test chứa số nguyên () là số đoạn của cây gậy. Dòng tiếp theo chứa số nguyên () là độ dài các đoạn theo đúng thứ tự xuất hiện trên cây gậy.
Sau bộ test cuối cùng là một dòng chứa duy nhất số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test và tổng diện tích lớn nhất có thể bao được khi gập cây gậy tại các khớp nối đã cho, theo dạng Case i: A (bộ test đánh số từ ). Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá .
Ràng buộc
- .
- , mọi là số nguyên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 2 3 4 8 3 4 5 33 3 4 3 5 0 |
Case 1: 4.898979 Case 2: 19.311 |
Bộ 1: tạo một tứ giác từ cả bốn đoạn, diện tích . Bộ 2: tam giác (diện tích ) và tứ giác (diện tích khoảng ), đoạn dài không được dùng. |
| 3 60 50 30 7 3 4 5 100 4 5 3 0 |
Case 1: 748.331478 Case 2: 12.000000 |
Bộ 1: tam giác có các cạnh . Bộ 2: hai tam giác và , mỗi tam giác có diện tích ; đoạn dài không được dùng. |
Bình luận