2019河北省大学生程序设计竞赛（重现赛）A.Battle of Balls（思维计算几何）

河北省大学生程序设计竞赛（重现赛）A.Battle of Balls（思维计算几何）"/>

2019河北省大学生程序设计竞赛（重现赛）A.Battle of Balls（思维计算几何）

题目链接：

题意：现在有一个矩形左上角坐标为 （ 0 ， 0 ） （0，0） （0，0），右下角坐标为 （ 100 ， 100 ） （100，100） （100，100）里面有 n n n个点，现在你有一个圆饼半径为 r r r，问你可不可以让饼从下边界进去，上边界出来并且不能碰到矩形中的点不能碰到矩形的边。

解题心得：

• 想到了就是个简单题没想到就会怀疑人生。首先点只有 1000 1000 1000个，现在枚举每两点之间的距离，如果两点之间的距离小于等于 2 ∗ r 2*r 2∗r，则将两点用并查集合并起来（可以看作连接一条直线），记录每个集合中最左边的 x x x坐标和最右边的 x x x坐标，这个时候圆只要能挨着矩形的左边或者右边过去就行了。这个想法看起来很不靠谱其实仔细想想这是非常正确的，因为并没有规定圆该怎么移动，只要不被最小的缝卡死就行了。
• 还有一个坑就是如果只有一个点这个时候是没有连线的，解决办法就是判断每个点和矩形的左右边界距离是否小于等于 2 ∗ r 2*r 2∗r，如果是的话就加一个点在边界上高度就是枚举的该点的高度。
  
  图画的有点丑大家不要笑话

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
const double esp = 1e-8;//防止精度被卡struct Point {double x, y;
} p[maxn];//记录每个点int n, father[maxn];//n个点，father用于并查集
double r;//定义半径void init() {scanf("%d%lf",&n, &r);r *= 2.0;//限制圆能否通过的是圆的直径for(int i=1;i<=n;i++) {scanf("%lf%lf", &p[i].x, &p[i].y);}int cnt = 1;for(int i=1;i<=n;i++) {//判断和边界之间的距离if(p[i].x - r <= esp) {p[n+cnt].x = 0;p[n+cnt].y = p[i].y;cnt++;}if((double(100.0) - p[i].x)  - r <= esp) {p[n+cnt].x = 100.0;p[n+cnt].y = p[i].y;cnt++;}}n += cnt-1;for(int i=1;i<=n;i++) father[i] = i;
}int find(int x) {if(x == father[x]) return x;return father[x] = find(father[x]);
}void merge(int x, int y) {int fx = find(x);int fy = find(y);if(fx != fy) father[fx] = fy;
}double get_dis(int u, int v) {double dis = (p[u].x - p[v].x) * (p[u].x - p[v].x) + (p[u].y - p[v].y) * (p[u].y - p[v].y);return dis;
}bool vis[maxn];
vector <pair<double, double> > ve;
void Merge() {for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++) {double dis = get_dis(i, j);if(dis-r*r <= esp) merge(i, j);//队友告诉我计算几何尽量不要用除法开方之类的东西，丢失精度严重}}for(int i=1;i<=n;i++) {int fi = find(i);double left_x = 10000.0, right_x = -10000.0;if(!vis[fi]) {//记录每一个集合是否被找过vis[fi] = true;for(int j=i;j<=n;j++) {int fj = find(j);if(fj == fi) {left_x = min(left_x, p[j].x);right_x = max(right_x, p[j].x);}}ve.push_back(make_pair(left_x, right_x));}}
}int main() {
//    freopen("1.in.txt", "r", stdin);int t; scanf("%d", &t);while(t--) {init();ve.clear();memset(vis, 0, sizeof vis);Merge();bool flag = false;for(int i=0;i<ve.size();i++) {if(ve[i].first - r<= esp && (double(100)-ve[i].second) - r <= esp) {flag = true;break;}}if(flag) {puts("No");} else {puts("Yes");}}return 0;
}