杭州网站搜索,如何安装wordpress的插件,网站生成移动版,sqlite3做网站数据库[NOIP2017 提高组] 奶酪
题目背景
NOIP2017 提高组 D2T1
题目描述
现有一块大奶酪#xff0c;它的高度为 h h h#xff0c;它的长度和宽度我们可以认为是无限大的#xff0c;奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系#xff0c;在坐标系…[NOIP2017 提高组] 奶酪
题目背景
NOIP2017 提高组 D2T1
题目描述
现有一块大奶酪它的高度为 h h h它的长度和宽度我们可以认为是无限大的奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系在坐标系中奶酪的下表面为 z 0 z 0 z0奶酪的上表面为 z h z h zh。
现在奶酪的下表面有一只小老鼠 Jerry它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交则 Jerry 可以从其中一个空洞跑到另一个空洞特别地如果一个空洞与下表面相切或是相交Jerry 则可以从奶酪下表面跑进空洞如果一个空洞与上表面相切或是相交Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道在不破坏奶酪的情况下能否利用已有的空洞跑 到奶酪的上表面去?
空间内两点 P 1 ( x 1 , y 1 , z 1 ) P_1(x_1,y_1,z_1) P1(x1,y1,z1)、 P 2 ( x 2 , y 2 , z 2 ) P2(x_2,y_2,z_2) P2(x2,y2,z2) 的距离公式如下 d i s t ( P 1 , P 2 ) ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 ( z 1 − z 2 ) 2 \mathrm{dist}(P_1,P_2)\sqrt{(x_1-x_2)^2(y_1-y_2)^2(z_1-z_2)^2} dist(P1,P2)(x1−x2)2(y1−y2)2(z1−z2)2
输入格式
每个输入文件包含多组数据。
第一行包含一个正整数 T T T代表该输入文件中所含的数据组数。
接下来是 T T T 组数据每组数据的格式如下 第一行包含三个正整数 n , h , r n,h,r n,h,r两个数之间以一个空格分开分别代表奶酪中空洞的数量奶酪的高度和空洞的半径。
接下来的 n n n 行每行包含三个整数 x , y , z x,y,z x,y,z两个数之间以一个空格分开表示空洞球心坐标为 ( x , y , z ) (x,y,z) (x,y,z)。
输出格式 T T T 行分别对应 T T T 组数据的答案如果在第 i i i 组数据中Jerry 能从下表面跑到上表面则输出 Yes如果不能则输出 No。
样例 #1
样例输入 #1
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4样例输出 #1
Yes
No
Yes提示
【输入输出样例 1 1 1 说明】 第一组数据,由奶酪的剖面图可见
第一个空洞在 ( 0 , 0 , 0 ) (0,0,0) (0,0,0) 与下表面相切
第二个空洞在 ( 0 , 0 , 4 ) (0,0,4) (0,0,4) 与上表面相切
两个空洞在 ( 0 , 0 , 2 ) (0,0,2) (0,0,2) 相切。
输出 Yes。
第二组数据,由奶酪的剖面图可见
两个空洞既不相交也不相切。
输出 No。
第三组数据,由奶酪的剖面图可见
两个空洞相交且与上下表面相切或相交。
输出 Yes。
【数据规模与约定】
对于 20 % 20\% 20% 的数据 n 1 n 1 n1 1 ≤ h 1 \le h 1≤h r ≤ 1 0 4 r \le 10^4 r≤104坐标的绝对值不超过 1 0 4 10^4 104。
对于 40 % 40\% 40% 的数据 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8 1 ≤ h 1 \le h 1≤h r ≤ 1 0 4 r \le 10^4 r≤104坐标的绝对值不超过 1 0 4 10^4 104。
对于 80 % 80\% 80% 的数据 1 ≤ n ≤ 1 0 3 1 \le n \le 10^3 1≤n≤103 1 ≤ h , r ≤ 1 0 4 1 \le h , r \le 10^4 1≤h,r≤104坐标的绝对值不超过 1 0 4 10^4 104。
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1 × 1 0 3 1 \le n \le 1\times 10^3 1≤n≤1×103 1 ≤ h , r ≤ 1 0 9 1 \le h , r \le 10^9 1≤h,r≤109 T ≤ 20 T \le 20 T≤20坐标的绝对值不超过 1 0 9 10^9 109。
AC代码
#includebits/stdc.h
using namespace std;typedef long long ll;
typedef pairint, intPII;
const int N3e510;
const int MOD9901;
const int INF0X3F3F3F3F;
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,-1,1,-1,1,-1,1};
const int M 1e6 10;int t;
int n, h, r;
int p[N];
struct q{int x;int y;int z;
}q[N];int finds(int x)
{if(p[x] ! x) p[x] finds(p[x]);return p[x];
}
int main()
{cin t;while(t --){cin n h r;for(int i 0; i n 1; i ) p[i] i;for(int i 1; i n; i ){int x, y, z;cin x y z;q[i] {x, y, z};if(abs(z) r) p[finds(i)] finds(0);if(abs(z - h) r) p[finds(i)] finds(n 1);//合并}for(int i 1; i n; i ){for(int j 1; j i; j )//j相当于是父亲{ll dx q[i].x - q[j].x;ll dy q[i].y - q[j].y;ll dz q[i].z - q[j].z;if(dx * dx dy * dy dz * dz (4 * (ll)r * r)){p[finds(i)] finds(j);}}}if(finds(0) finds(n 1)) puts(Yes);else puts(No);}
}
