直接遍历所有圆,选取 圆周外面多一点点的地方 去测试能否选取,因为 n 很小,所以我们可以选很多点去测试,对于每个圆,按角度从圆心0~360度的方向往外多一些距离选点,然后判断这个点是否在地图内,是否被某个圆覆盖。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
double dis(double x1,double y1,double x2,double y2){
double dx=abs(x1-x2),dy=(y1-y2);
return sqrt(dx*dx+dy*dy);
}
using tiii=tuple<double,double,double>;
int main() {
int n,l;cin>>n>>l;
double epslon=1e-6;
double delta=1e-3;
vector<tiii> a(n+1);
for(int i=1;i<=n;i++){
int x,y,r;cin>>x>>y>>r;
a[i]={x,y,r};
}
auto check=[&](double _x,double _y){
if(_x<0||_x>l||_y<0||_y>l)return false;
for(auto [x,y,r]:a){
if(dis(x,y,_x,_y)<=r+epslon)return false;
}
return true;
};
for(int i=1;i<=n;i++){
auto [x,y,r]=a[i];
for(int j=1;j<=359000;j++){
double cur_x=x+r*cos(j/1000.0)+delta;
double cur_y=y+r*sin(j/1000.0)+delta;
if(check(cur_x,cur_y)){
cout<<fixed<<setprecision(10)<<cur_x<<' '<<cur_y<<endl;
return 0;
}
}
}
return 0;
}
// 64 位输出请用 printf("%lld")

京公网安备 11010502036488号