题意：给你n个圆和一条线段，保证圆和圆、圆和线段所在直线不相交，不相切，不包含。求一个过线段两端点的圆，满足不和任何圆相交（可以相切、包含）。问圆的最小半径。
n<=100000
思路
求解圆与圆相切考虑圆反演，如果我们以线段一个点P1为反演圆的圆心，反演，那么所求的圆变为一条直线且过线段另一个点的反演点P2。当直线垂直与P1P2时，所求圆的半径最小。但是直线不能穿过其他圆的反演，所以要么直线垂直与P1P2，要么直线是P1到某个圆的反演的切线，以P1为中心对切线极坐标排序，扫描线即可。
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define double long double
const double pi=acos(-1.0);
const double esp=1e-8;
const double inf=1e100;
bool cmp0(double x){return fabs(x)<esp;}
int cmp(double x){return cmp0(x)?0:x>0?1:-1;}
double acs(double x){if(cmp0(x-1))x=1;if(cmp0(x+1))x=-1;return acos(x);}
struct point{//点/向量
double x,y;
void in(){scanf("%Lf %Lf",&x,&y);}
void out(){printf("%lf %lf\n",x,y);}
point(double xx=0,double yy=0){x=xx,y=yy;}
point operator + (const point& a)const{return point(x+a.x,y+a.y);}
point operator - (const point& a)const{return point(x-a.x,y-a.y);}
point operator * (const double& a)const{return point(x*a,y*a);}
point operator / (const double& a)const{return point(x/a,y/a);}
double operator *(const point& a)const{return x*a.x+y*a.y;}
double operator ^(const point& a)const{return x*a.y-y*a.x;}
bool operator < (const point& a)const{return x==a.x?y<a.y:x<a.x;}
};
double len1(const point& a){return sqrt(a*a);} //向量模长
double len2(const point& a){return a*a;}//向量模长平方
bool cmp1(const point& a,const point& b){return a.x==b.x?a.y<b.y:a.x<b.x;}//坐标排序
bool cmp2(const point& a,const point& b){return a.y==b.y?a.x<b.x:a.y<b.y;}//坐标排序
double cro(const point& a,const point& b,const point& o){return (a-o)^(b-o);} //叉积
int qua(const point& a)//象限
{
if(a.x==0&&a.y==0) return 0;
if(a.x>=0&&a.y>=0) return 1;
if(a.x<=0&&a.y>=0) return 2;
if(a.x<=0&&a.y<=0) return 3;
return 4;
}
bool cmp3(const point& a,const point& b){//极角序 *排序
return qua(a)==qua(b)?(a^b)<0:qua(a)<qua(b);
}
double rad(point a){a=a/len1(a);return a.y>0?acos(a.x):-acos(a.x);}//向量弧度
point rotate(const point& a,double ang){//顺时针
return point(a.x*cos(ang)+a.y*sin(ang),-a.x*sin(ang)+a.y*cos(ang));
}
point rotate(const point& a,const point& b,double ang){//a绕b转
return b+rotate(a-b,ang);
}
struct line{
point s,t,v;//直线/线段/射线
line(){}//s起点，t终点，v向量(t-s)
line(const point& ss,const point& tt){s=ss,t=tt,v=t-s;}
};
point pro(const line& a,const point& b){// b在a上的投影
point a1=a.t-a.s,a2=b-a.s;
return a.s+(a1*((a1*a2)/(a1*a1)));
}
point ref(const line& a,const point& b){// b在a上的反射
return pro(a,b)*2-b;
}
// 点与直线/线段/射线关系
bool on_line(const line& a,const point& b){return cmp0(a.v^(a.t-b));}
bool on_ray(const line& a,const point& b){return on_line(a,b)&&(a.v*(b-a.s)>=-esp);}
bool on_seg(const line& a,const point& b){return on_line(a,b)&&((a.t-b)*(b-a.s)>=-esp);}
int parall(const line& a,const line& b){// 线线关系
if((a.v^b.v)==0) return 1;//平行
if(a.v*b.v==0) return 2;//垂直
else return 0;
}
point inter_line(const line& a,const line& b)//直线交点
{
double k=((b.s-a.s)^b.v)/(a.v^b.v);
return a.s+a.v*k;
}
bool inter_seg(const line& a,const line& b)//线段交 **
{
if(parall(a,b)==1) return on_seg(a,b.s)||on_seg(a,b.t)||on_seg(b,a.s)||on_seg(b,a.t);
point f=inter_line(a,b);
return on_seg(a,f)&&on_seg(b,f);
}
double dis_segp(const line &a,const point& b)//点到线段距离**
{
point p=pro(a,b);
if(on_seg(a,p)) return len1(pro(a,b)-b);
return min(len1(a.s-b),len1(a.t-b));
}
struct circle{
point o;double r;
circle(){}
circle(point oo,double rr){o=oo,r=rr;}
double area()const{return r*r*pi;}
bool in(const point& a){return len1(a-o)-r<=esp;}
};
void tangent(const circle& c,const point& a,point& p1,point& p2)//圆切线
{
double d=len1(c.o-a);
double cos=c.r/d;
double sin=sqrt(1-cos*cos);
point d1=(a-c.o)*(cos*c.r/d);
point d2=(a-c.o)*(sin*c.r/d);swap(d2.x,d2.y);d2.y=-d2.y;
p1=c.o+d1+d2,p2=c.o+d1-d2;
}
// 圆反演
point inversion(const circle& o,const point& a)//p->p
{
return o.o+(a-o.o)*o.r*o.r/len1(o.o-a)/len1(o.o-a);
}
circle inversion(const circle& o,const line& a)//line->circle
{
circle b;point c=pro(a,o.o);
b.r=o.r*o.r/len1(o.o-c)/2;
b.o=o.o+(c-o.o)/len1(c-o.o)*b.r;
return b;
}
circle inversion(const circle& o,const circle& a)//circlr->circle
{
circle b;
double oa=len1(o.o-a.o);
b.r=(1.0/(oa-a.r)-1.0/(oa+a.r))*o.r*o.r/2;
double ob=oa*b.r/a.r;
b.o=o.o+(a.o-o.o)*ob/oa;
return b;
}
circle c[100005];
bool cmpp(pair<point,int> a,pair<point,int> b)
{
if(len1(a.first-b.first)==0) return a.second>b.second;
return cmp3(a.first,b.first);
}
int main()
{
double ans=1e18;
point p1,p2;
p1.in(),p2.in();
circle o(p1,100000);
p2=inversion(o,p2);
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
c[i].o.in();
scanf("%Lf",&c[i].r);
c[i]=inversion(o,c[i]);
}
point px1,px2;
vector<pair<point,int> > v;
v.push_back(make_pair(point(-(p2-p1).y,(p2-p1).x),1));
v.push_back(make_pair(point(-(p2-p1).y,(p2-p1).x),-1));
for(int i=1;i<=n;i++)
{
tangent(c[i],p2,px1,px2);
v.push_back(make_pair(px1-p2,1));
v.push_back(make_pair(px2-p2,-1));
v.push_back(make_pair(p2-px1,1));
v.push_back(make_pair(p2-px2,-1));
}
sort(v.begin(),v.end(),cmpp);
int cur=0,minc=0;
for(int i=0;i<v.size();i++) cur+=v[i].second,minc=min(minc,cur);
cur-=minc;
for(int i=0;i<v.size();i++)
{
if((cur==0&&v[i].second==1)||(cur==1&&v[i].second==-1))
{
double d=len1(o.o-pro(line(p2,v[i].first+p2),o.o));
circle anscir=inversion(o,line(p2,v[i].first+p2));
ans=min(ans,anscir.r);
}
cur+=v[i].second;
}
printf("%.10Lf\n",ans);
return 0;
}
评论区