HBC16417[NOIP2017]奶酪题解（奶酪中的空间坐标系）

人生如戏算法基础篇 2023-11-09 05:44:02 95 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞，我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z = 0，奶酪的上表面为 z = h。

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z = 0，奶酪的上表面为 z = h。现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交， Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交， Jerry 则可以从空洞跑到奶酪上表面。位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去? 空间内两点 P1(x1,y1,z1) 、P2(x2,y2,z2) 的距离公式如下： dist(P_1,P_2)=sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} dist(P 1 ,P 2 )= (x 1 −x 2 ) 2 +(y 1 −y 2 ) 2 +(z 1 −z 2 ) 2