trang chủ / đề bài / icpcwf11_g

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 n (1≤n≤500) là số đoạn của cây gậy. Dòng tiếp theo chứa n số nguyên S1,S2,…,Sn (1≤Si≤1000) 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ố 0.

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ừ 1). Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá 10−4.

Ràng buộc

  • 1≤n≤500.
  • 1≤Si≤1000, mọi Si 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 24≈4.898979. Bộ 2: tam giác 3,4,5 (diện tích 6) và tứ giác 3,4,3,5 (diện tích khoảng 13.311), đoạn dài 33 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 60,50,30. Bộ 2: hai tam giác 3,4,5 và 4,5,3, mỗi tam giác có diện tích 6; đoạn dài 100 không được dùng.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0