GYM 101617 F

时间:2021-06-28 07:09:16

说到这题还要提到周日下午训练赛,都进去了hmc说他这场单切过准备换一场。

很不幸的是我当时已经开了这个几何题,

开场就开几何是什么鬼啊!!!

给你n个圆,找一点在所有园内并且离原点最远。(保证有解)

我们肯定要援圆交啦!要素过多

其实我们可以大胆的猜测这个答案就在圆的交点上,

但是我们考虑到某种特殊情况,比方说只有一个圆,所以求一下原点与圆心的连线与圆的交点

再考虑到可能圆心就在原点上,特判一下,就ok了

 //
// Created by gtx1080 on 2019-04-23.
//
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
int operator == (const point &k1) const{return cmp(x,k1.x)==&&cmp(y,k1.y)==;}
db abs(){return sqrt(x*x+y*y);}
db abs2(){return x*x+y*y;}
db dis(point k1){return ((*this)-k1).abs();}
point turn90(){return (point){-y,x};}
point unit(){db w=abs(); return (point){x/w,y/w};}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
point proj(point k1,point k2,point q){ // q 到直线 k1,k2 的投影
point k=k2-k1; return k1+k*(dot(q-k1,k)/k.abs2());
}
struct circle{
point o; db r;
int inside(point k){return cmp(r,o.dis(k))>=;}
};
int checkposCC(circle k1,circle k2){// 返回两个圆的公切线数量
if (cmp(k1.r,k2.r)==-) swap(k1,k2);
db dis=k1.o.dis(k2.o); int w1=cmp(dis,k1.r+k2.r),w2=cmp(dis,k1.r-k2.r);
if (w1>) return ; else if (w1==) return ; else if (w2>) return ;
else if (w2==) return ; else return ;
}
vector<point> getCC(circle k1,circle k2){// 沿圆 k1 逆时针给出 , 相切给出两个
int pd=checkposCC(k1,k2); if (pd==||pd==) return {};
db a=(k2.o-k1.o).abs2(),cosA=(k1.r*k1.r+a-k2.r*k2.r)/(*k1.r*sqrt(max(a,(db)0.0)));
db b=k1.r*cosA,c=sqrt(max((db)0.0,k1.r*k1.r-b*b));
point k=(k2.o-k1.o).unit(),m=k1.o+k*b,del=k.turn90()*c;
return {m-del,m+del};
}
vector<point> getCL(circle k1,point k2,point k3){ // 沿着 k2->k3 方向给出 , 相切给出两个
point k=proj(k2,k3,k1.o); db d=k1.r*k1.r-(k-k1.o).abs2();
if (sign(d)==-) return {};
point del=(k3-k2).unit()*sqrt(max((db)0.0,d)); return {k-del,k+del};
}
vector<point> mb,tmp;
void slove(circle a,circle b){
if(checkposCC(a,b)){
tmp = getCC(a,b);
mb.push_back(tmp[]);
mb.push_back(tmp[]);
}
}
void check(circle a){
if(a.o==(point){,})
return;
tmp = getCL(a,{,},a.o);
mb.emplace_back(tmp[]);
mb.emplace_back(tmp[]);
}
int n;circle c[];
db solve(point x){
for(int i=;i<=n;i++){
if(!c[i].inside(x))
return ;
}
return x.abs();
}
int main(){
scanf("%d",&n);
db nxt=;
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&c[i].o.x,&c[i].o.y,&c[i].r);
if(c[i].o==(point){,})nxt=min(nxt,c[i].r);
}
for(int i=;i<=n;i++){
check(c[i]);
for(int j=i+;j<=n;j++){
slove(c[i],c[j]);
}
}
db ans = ;
for(auto tmp:mb){
// printf("%.11f %.11f\n",tmp.x,tmp.y);
ans = max(ans,solve(tmp));
}
if(cmp(ans,)==&&nxt!=)
printf("%.3f\n",nxt);
else
printf("%.3f\n",ans);
}