并查集。
若两点之间距离小于 就建边。
最后判断每个点所属连通块是否与点 一致即可。
for (LL i = 1; i <= n; i ++){
for (LL j = 1; j <= i - 1; j ++){
if (sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])) <= D)
fa[Find(i)] = Find(j);
}
}
for (LL i = 1; i <= n; i ++){
if (Find(i) == Find(1))
cout << "Yes\n";
else
cout << "No\n";
}
upper_bound
查找出每个点所处方格的行号 与列号 ,再计算出其所处方格编号 。然后按照编号排序,统计相同编号的蛋糕个数最值即可,注意判断是否会有空方格。
for (LL i = 1; i <= n; i ++){
LL a = upper_bound(A + 1, A + Len1 + 2, Point[i].x) - A;
LL b = upper_bound(B + 1, B + Len2 + 2, Point[i].y) - B;
Point[i].K = a * (Len2 + 1) + b;
mp[Point[i].K] ++;
}
sort(Point + 1, Point + 1 + n, cmp);
Point[n + 1].K = -1e18;
LL cnt = 1, Min = n + 1, Max = 0, t = 0;
for (LL i = 2; i <= n + 1; i ++){
if (Point[i].K == Point[i - 1].K)
++ cnt;
else{
Min = min(Min, cnt);
Max = max(Max, cnt);
++ t;
cnt = 1;
}
}
if (t < (Len1 + 1) * (Len2 + 1)){
Min = 0;
}
cout << Min << " " << Max << "\n";
并查集预处理连通块。
将 个点对所处两个连通块对存入集合:
对于询问,若询问的点对所处连通块对 能在集合中找到,则输出 No
,否则输出 Yes
。
for (LL i = 1; i <= m; i ++){
cin >> x >> y;
fa[Find(x)] = Find(y);
}
cin >> K;
set<pair<LL, LL> > s;
for (LL i = 1; i <= K; i ++){
cin >> x >> y;
s.insert(make_pair(Find(x), Find(y)));
}
cin >> Q;
for (LL i = 1; i <= Q; i ++){
cin >> x >> y;
if (s.count(make_pair(Find(x), Find(y))) || s.count(make_pair(Find(y), Find(x))))
cout << "No\n";
else
cout << "Yes\n";
}