简答题 偏难
#23342

奶酪 【问题描述】 现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,…

奶酪

【问题描述】

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

现在,奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交,Jerry 则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?

【输入格式】

输入文件名为 cheese.in。

每个输入文件包含多组数据。

输入文件的第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。

接下来是 T 组数据,每组数据的格式如下:

第一行包含三个正整数 n,h 和 r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。

接下来的 n 行,每行包含三个整数 x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(x, y, z)。

【输出格式】

输出文件名为 cheese.out。

输出文件包含 T 行,分别对应 T 组数据的答案,如果在第 i 组数据中,Jerry 能从下

表面跑到上表面,则输出“Yes”,如果不能,则输出“No”(均不包含引号)。

【输入输出样例 1】

【输入输出样例 1 说明】

【数据规模与约定】

对于 20%的数据,n = 1,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。

对于 40%的数据,1 ≤ n ≤ 8, 1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。

对于 80%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。

对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 1,000,000,000,T ≤ 20,坐标的绝对值不超过 1,000,000,000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">#define rg register int</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">long long T, n, h, r, x[1005], y[1005], z[1005], f[1005][1005], bz[1005], ans;</p><p style="text-align: left;">int dist(int i, int j) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>double s = sqrt((x[i] - x[j]) * 1.0 * (x[i] -x [j])*1.0 + (y[i] - y[j]) * 1.0 * (y[i] - y[j])*1.0 + (z[i] - z[j]) * 1.0 * (z[i] -z [j]) * 1.0) * 1.0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (s &gt; (int)s) s++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return s;</p><p style="text-align: left;">}</p><p style="text-align: left;">void dfs(int x) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (x == n + 1) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>bz[x] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (rg i = 1; i &lt;= n + 1; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (f[x][i] &amp;&amp; (!bz[i])) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(i);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (ans == 1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">int main() {</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%lld", &amp;T);</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (T--) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%lld%lld%lld", &amp;n, &amp;h, &amp;r), ans = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (rg i = 1; i &lt;= n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%lld%lld%lld", &amp;x[i], &amp;y[i], &amp;z[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (rg i = 0; i &lt;= n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(rg j = i + 1; j &lt;= n+1; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[i][j] = f[j][i] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (rg i = 1; i &lt;= n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (rg j = i + 1; j &lt;= n; j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (dist(i,j) &lt;= r * 2) f[i][j] = f[j][i] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (rg i = 1; i &lt;= n; i++) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>bz[i] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (h - z[i] &lt;= r) f[i][n + 1] = f[n + 1][i] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (z[i] &lt;= r) f[i][0] = f[0][i] = 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (ans) printf("Yes\n");</p><p style="text-align: left;"><span style="white-space:pre"> </span>else printf("No\n");</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。