链接 ： https://codeforces.com/gym/101955/problem/L
本来是过了的…但看了大佬的代码之后开始怀疑自己是怎么卡过去的
大佬的代码：
#include <bits/stdc++.h> using namespace std; const double Pi=acos(-1); const double eps=1e-12; const int N=1e5+5; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y) {}; }; Point operator +(Point A,Point B) { return Point(A.x+B.x,A.y+B.y); } Point operator -(Point A,Point B) { return Point(A.x-B.x,A.y-B.y); } Point operator *(Point A,double B) { return Point(A.x*B,A.y*B); } Point operator /(Point A,double B) { return Point(A.x/B,A.y/B); } int dcmp(double x) { if(fabs(x)<eps)return 0; return x<0?-1:1; } bool operator<(const Point&a,const Point&b) { return a.x<b.x||(a.x==b.x&&a.y<b.y); } bool operator == (const Point &a,const Point &b) { return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; } double Dot(Point A,Point B) { return A.x*B.x+A.y*B.y; } double Length(Point A) { return sqrt(Dot(A,A)); } double Cross(Point A,Point B) { return A.x*B.y-A.y*B.x; } double Angle(Point A,Point B) {//利用点积 求出向量 A B 的夹角 cos值 return acos(Dot(A,B)/Length(A)/Length(B)); } double Angle(Point A) { return atan2(A.y, A.x); } struct Circle { //圆 Point c; double r; Circle(Point c = Point(0, 0), double r = 0):c(c),r(r) {} Point point(double a) { return Point(c.x+cos(a)*r,c.y+sin(a)*r); } }; double dis(Point A,Point B) { return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); } int circle_circle(Circle C1,Circle C2,vector<Point>&sol) { //圆与圆的交点，核心思想就是利用余弦定理求出两交点与圆心连线的夹角，显然可以根据已知距离，和圆心坐标，求出交点坐标，不同去画图，高中几何知识 double d=Length(C1.c-C2.c); if(dcmp(d)==0) { if(dcmp(C1.r-C2.r)==0)return -1; return 0; } if(dcmp(C1.r+C2.r-d)<0)return 0; if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0; double a=Angle(C2.c-C1.c); double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*d*C1.r)); Point p1=C1.point(a-da),p2=C1.point(a+da); sol.push_back(p1); if(p1==p2)return 1; sol.push_back(p2); return 2; } //由此往上的全部，即为两圆交点模板 //解方程无法换算不同的精度，而该方法可以有不同的eps，且精度和速度都比解方程更优秀 int T,n; double R; Point p[N]; double r[N]; int check(Point A) { for(int i=1; i<=n; i++) { double h=dis(A,p[i]); if(h<r[i]+eps)return 0; } return 1; } int main() { cin>>T; int kase=0; while(T--) { cin>>n>>R; Circle C0; C0.c=Point(0,0); C0.r=R; vector<Point>v; for(int i=1; i<=n; i++) { double x,y,z; scanf("%lf%lf%lf",&x,&y,&z); p[i]=Point(x,y); r[i]=z; Circle C1; C1.c=Point(x,y); C1.r=z; circle_circle(C0,C1,v); } double ans=0; int f=0; for(int i=0; i<v.size(); i++) { double x=-v[i].x; double y=-v[i].y; if(check(Point(x,y))) { f=1; break; } } if(f or v.size()==0) { printf("Case #%d: %.10lf\n",++kase,R*2); continue; } int h=v.size(); for(int i=0; i<h; i++) { for(int j=0; j<h; j++) { if(i==j)continue; double res=dis(v[i],v[j]); ans=max(ans,res); } } printf("Case #%d: %.15lf\n",++kase,ans); } return 0; }
