trang chủ / đề bài / icpcwf15_d

Cắt phô mai

Đề bài

Mô tả

Chắc hẳn ai cũng đã nghe nói về Công ty Chế biến Phô mai Quốc tế (International Cheese Processing Company). Chiếc máy cắt một khối phô mai thành các lát có độ dày bằng hệt nhau của họ đã trở thành kinh điển. Gần đây họ làm ra một chiếc máy có thể cắt một khối phô mai hình cầu (như phô mai Edam) thành các lát, không phải các lát dày bằng nhau, mà là các lát nặng bằng nhau! Nhưng thử thách mới đang chờ phía trước: cắt phô mai Thụy Sĩ.

Phô mai Thụy Sĩ như Emmentaler có các lỗ hổng bên trong, và các lỗ có thể có kích thước khác nhau. Một lát có lỗ chứa ít phô mai hơn và nhẹ hơn một lát không có lỗ. Vì vậy thử thách là: cắt một khối phô mai có lỗ thành các lát có khối lượng bằng nhau.

Nhờ các kỹ thuật sóng âm thông minh (cùng loại kỹ thuật dùng để siêu âm thai nhi và dò tìm mỏ dầu), người ta có thể xác định vị trí các lỗ trong phô mai với độ chính xác tới micromet. Trong bài này, bạn có thể giả sử các lỗ là những hình cầu hoàn hảo.

Mỗi khối phô mai chưa cắt có kích thước 100×100×100, mỗi chiều đo bằng milimet. Nhiệm vụ của bạn là cắt khối đó thành s lát có khối lượng bằng nhau. Các lát sẽ rộng 100 mm và cao 100 mm, và bạn cần xác định độ dày của từng lát.

Khối phô mai chiếm các điểm (x,y,z) với 0≤x,y,z≤100000 (đơn vị micromet), trừ các điểm thuộc một lỗ nào đó. Các nhát cắt vuông góc với trục z. Phô mai đồng chất, nên khối lượng của một lát tỉ lệ với thể tích phô mai trong lát đó.

Bạn có thể giả sử các lỗ không chồng lên nhau nhưng có thể tiếp xúc nhau, và các lỗ nằm hoàn toàn bên trong khối phô mai nhưng có thể tiếp xúc với mặt ngoài của khối.

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên n và s, trong đó n là số lỗ trong khối phô mai và s là số lát cần cắt. Mỗi dòng trong n dòng tiếp theo gồm bốn số nguyên dương r, x, y và z mô tả một lỗ: r là bán kính và (x,y,z) là tọa độ tâm của lỗ, tất cả đều tính bằng micromet.

Dữ liệu ra

In ra s độ dày của các lát, tính bằng milimet, mỗi số trên một dòng, bắt đầu từ đầu khối phô mai có z=0. Mỗi số được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6.

Ràng buộc

  • 0≤n≤10000, 1≤s≤100.
  • r, x, y, z là số nguyên dương; mỗi lỗ nằm hoàn toàn trong khối: r≤x,y,z≤100000−r.
  • Các lỗ không chồng lên nhau (có thể tiếp xúc).

Ví dụ

Input Output Giải thích
0 4 25.000000000
25.000000000
25.000000000
25.000000000
Không có lỗ: bốn lát nặng bằng nhau thì dày bằng nhau, mỗi lát 100/4=25 mm.
2 5
10000 10000 20000 20000
40000 40000 50000 60000
14.611103142
16.269801734
24.092457788
27.002992272
18.023645064
Lỗ thứ nhất bán kính 10 mm, chiếm 10≤z≤30 mm; lỗ thứ hai bán kính 40 mm, chiếm 20≤z≤100 mm. Các lát đi qua phần rộng của lỗ lớn chứa ít phô mai trên mỗi milimet nên phải dày hơn. Tổng độ dày là 100 mm.

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