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 , mỗi chiều đo bằng milimet. Nhiệm vụ của bạn là cắt khối đó thành lát có khối lượng bằng nhau. Các lát sẽ rộng mm và cao 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 với (đơ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 . 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 và , trong đó là số lỗ trong khối phô mai và là số lát cần cắt. Mỗi dòng trong dòng tiếp theo gồm bốn số nguyên dương , , và mô tả một lỗ: là bán kính và là tọa độ tâm của lỗ, tất cả đều tính bằng micromet.
Dữ liệu ra
In ra độ 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ó . 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á .
Ràng buộc
- , .
- , , , là số nguyên dương; mỗi lỗ nằm hoàn toàn trong khối: .
- 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 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 mm, chiếm mm; lỗ thứ hai bán kính mm, chiếm 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à mm. |
Bình luận