trang chủ / đề bài / icpcwf10_k

Chặn giấy

Đề bài

Mô tả

Công ty của bạn sản xuất các chặn giấy nghệ thuật. Mỗi chặn giấy là hợp của hai tứ diện có chung một mặt. Chúng được làm bằng thủy tinh đặc trong suốt, bên trong có gắn các hạt màu nhỏ. Một trong các hạt nhỏ đó thực ra là một con chip RFID rất nhỏ. Con chip này phải được đặt gần một máy tính đi kèm thì máy tính đó mới hoạt động được. Thông thường điều này được thực hiện bằng cách đặt chặn giấy lên nóc máy tính. Tuy nhiên tầm hoạt động của con chip có hạn, nên khoảng cách từ chip tới mặt phẳng nóc máy tính rất quan trọng. Vì vậy cần tính khoảng cách nhỏ nhất và lớn nhất có thể từ chip tới nóc máy tính khi chặn giấy được đặt ở một vị trí đủ vững. Một vị trí được coi là đủ vững nếu chặn giấy vẫn không dịch chuyển khi trọng tâm của nó bị dời đi một khoảng tối đa 0.2 đơn vị theo bất kỳ hướng nào. Có thể giả sử chặn giấy có khối lượng riêng đồng đều và con chip đủ nhỏ để coi là một điểm.

Hình 1

Hình 2

Ví dụ, xét một chặn giấy có các đỉnh của mặt chung là A=(0,0,0), B=(9,0,0), C=(0,8,0), đỉnh thứ tư của một tứ diện là D=(0,0,9), đỉnh thứ tư của tứ diện còn lại là E=(1,1,−8), và con chip ở F=(1,2,−1) (xem Hình 1, con chip được vẽ bằng chấm nhỏ). Đặt chặn giấy với mặt BCD nằm trên máy tính cho khoảng cách lớn nhất, xấp xỉ 3.7 (phần trên của Hình 2). Đặt chặn giấy với mặt ACD nằm trên máy tính cho khoảng cách nhỏ nhất là 1.0 (phần dưới của Hình 2). Đặt chặn giấy với mặt ACE nằm trên máy tính cho khoảng cách chỉ 0.9 nhưng vị trí đó không đủ vững.

Dữ liệu vào

Dữ liệu vào gồm một hoặc nhiều bộ test. Mỗi bộ test nằm trên một dòng, mô tả sáu điểm A, B, C, D, E và F theo đúng thứ tự đó. Mỗi điểm được mô tả bằng ba số nguyên x, y, z là tọa độ của nó. Hai tứ diện ABCD và ABCE đều có thể tích dương, D và E nằm ở hai phía khác nhau của mặt phẳng đi qua A, B, C, và điểm F nằm hẳn bên trong chặn giấy. Luôn tồn tại ít nhất một cách đặt chặn giấy ở vị trí đủ vững.

Dữ liệu vào kết thúc bằng một dòng chỉ chứa số nguyên 0.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test, tiếp theo là khoảng cách nhỏ nhất và lớn nhất từ con chip tới mặt phẳng đáy (nóc máy tính) khi chặn giấy được đặt ở vị trí đủ vững. Các số này được làm tròn và in với đúng năm chữ số sau dấu thập phân. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • Mọi tọa độ có giá trị tuyệt đối không vượt quá 1000.
  • Mỗi file có không quá 104 bộ test.

Ví dụ

Input Output Giải thích
0 0 0 9 0 0 0 8 0 0 0 9 1 1 -8 1 2 -1
0 0 0 7 0 0 0 7 0 0 0 7 -1 -2 -3 2 2 2
1 2 3 6 2 3 -2 6 3 -1 0 7 4 1 -2 -1 5 3
0
Case 1: 1.00000 3.73526
Case 2: 0.57735 2.66967
Case 3: 0.28214 5.00871
Bộ 1 là ví dụ trong đề (Hình 1 và Hình 2). Bộ 3: con chip nằm trên mặt chung ABC, vẫn ở bên trong chặn giấy.
0 0 0 6 0 0 4 7 0 7 0 6 0 0 -6 4 2 1
0 0 0 6 0 0 0 6 0 -1 -1 3 -1 -1 -3 1 0 1
0
Case 1: 1.03115 2.00000
Case 2: 0.70711 2.53993
Bộ 1: A, B, D, E cùng nằm trên mặt phẳng y=0, chân đế là tứ giác có bốn đỉnh đó. Trọng tâm (3.375,1.75,0) chiếu xuống tại (3.375,0,0), cách mọi cạnh của tứ giác hơn 0.2, nên vị trí này đủ vững và cho khoảng cách lớn nhất 2 (điểm chiếu nằm trên cạnh AB của các tam giác ABD, ABE và rất gần cạnh DE, nên không thể chỉ xét từng tam giác). Bộ 2: hợp hai tứ diện không lồi, chặn giấy có thể nằm trên mặt BDE (không phải mặt của tứ diện nào), cho khoảng cách nhỏ nhất 0.70711.

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