trang chủ / đề bài / icpcwf07_h

Nâng mái nhà

Đề bài

Mô tả

Bạn đồng ý giúp một thợ lợp mái ước lượng lượng vật liệu cần dùng để bảo vệ bề mặt mái nhà khỏi tác hại của ánh nắng, bằng cách tính diện tích bề mặt mái nhà có thể nhìn thấy khi nhìn từ trên thẳng xuống.

Hình dạng của mái nhà được xác định bởi các đỉnh của các tam giác bao quanh các mặt phẳng của mái. Toạ độ x và y của một đỉnh được xác định từ ảnh chụp mái nhà từ trên không, còn toạ độ z là độ cao của đỉnh so với mặt đất, giả sử mặt đất bằng phẳng (và đúng là như vậy). Ví dụ, đoạn thẳng có hai đầu (10,10,10) và (10,20,10) song song với mặt đất và dài 10 đơn vị. Đoạn thẳng có hai đầu (10,10,10) và (10,18,16) dốc lên từ độ cao 10 tới độ cao 16 so với mặt đất; trên ảnh chụp từ trên không nó dài 8 đơn vị, nhưng độ dài thật là 10 đơn vị.

Trên ảnh chụp từ trên không, đôi khi một vùng của mái nhà che khuất một vùng thấp hơn. Chỉ những phần nhìn thấy được của mái nhà mới được tính vào tổng. Ví dụ, giả sử bạn nhìn một toà nhà hai tầng có tầng hai nhỏ hơn tầng một. Hiển nhiên diện tích mái của tầng hai phải được tính vào tổng, nhưng phần diện tích nhìn thấy được của mái tầng một không bao gồm phần nằm ngay bên dưới mái tầng hai.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, mỗi bộ test mô tả một mái nhà. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên V là số đỉnh và T là số tam giác. Mỗi dòng trong V dòng tiếp theo chứa ba toạ độ x, y, z của một đỉnh. Bộ test kết thúc bằng T dòng mô tả tam giác, mỗi dòng gồm ba chỉ số đỉnh là ba đỉnh của một tam giác của mái. Các đỉnh được đánh số liên tiếp theo thứ tự xuất hiện trong dữ liệu, bắt đầu từ 1.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự bộ test (bắt đầu từ 1) và tổng diện tích bề mặt nhìn thấy được của mái nhà, chính xác tới hai chữ số sau dấu thập phân, theo định dạng của ví dụ. In một dòng trống sau kết quả của mỗi bộ test.

Ràng buộc

  • 1≤V≤300, 1≤T≤1000.
  • Mọi toạ độ là số nguyên dương không quá 100.
  • Không có tam giác nào suy biến, và phần trong của hai tam giác bất kỳ không giao nhau: chúng có thể chạm nhau nhưng không chồng lên hay cắt nhau.
  • Mỗi file có không quá 100 bộ test và tổng T trong một file không quá 5000.
  • Trong mọi bộ test, diện tích chính xác cách mọi giá trị (k+0.5)/100 (k nguyên) ít nhất 10−6.

Ví dụ

Input Output Giải thích
6 2
10 10 10
10 20 10
20 10 10
10 10 20
10 20 20
20 20 20
1 2 3
4 5 6
3 1
10 10 10
10 18 16
20 10 10
1 2 3
0 0
Case 1: 75.00

Case 2: 50.00
Bộ 1: tam giác thứ hai (cao 20) che một nửa tam giác thứ nhất (cao 10), mỗi tam giác có diện tích 50: 50+25=75. Bộ 2: hình chiếu có diện tích 40, mặt nghiêng có diện tích 50.
8 4
10 10 10
30 10 10
30 30 10
10 30 10
15 15 20
25 15 20
25 25 20
15 25 20
1 2 3
1 3 4
5 6 7
5 7 8
4 2
10 10 10
10 40 10
40 10 10
40 40 40
1 2 3
1 2 4
3 1
10 10 10
20 20 10
15 15 50
1 2 3
6 2
10 10 1
50 10 1
30 50 90
20 12 30
40 12 30
30 20 30
1 2 3
4 5 6
0 0
Case 1: 400.00

Case 2: 861.40

Case 3: 0.00

Case 4: 1836.36
Bộ 1: toà nhà hai tầng, mái tầng một 20×20, mái tầng hai 10×10: 400−100+100. Bộ 2: hai tam giác chung cạnh nối (10,10) với (10,40); tam giác nghiêng (mặt z=x) nằm trên một phần của tam giác nằm ngang: 4502+225≈861.40. Bộ 3: tam giác thẳng đứng, không nhìn thấy gì. Bộ 4: tam giác phẳng ở độ cao 30 nằm trên phần thấp của một tam giác rất dốc (dù tam giác dốc có đỉnh cao tới 90).

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