AtCoder Beginner Contest 157 F Yakiniku Optimization Problem 难点 计算几何 求解两圆相交的交点坐标 二分

AtCoder Beginner Contest 157   比赛人数7464   与codeforces比赛冲突，遗憾没有参加实时赛，之后模拟赛，打得没劲AtCoder

AtCoder Beginner Contest 157 F Yakiniku Optimization Problem  难点 计算几何 求解两圆相交的交点坐标  二分

总目录详见https://blog.csdn.net/mrcrack/article/details/104454762

在线测评地址https://atcoder.jp/contests/abc157/tasks/abc157_f

样例1模拟如下图所示

思路同https://blog.csdn.net/huah_2018/article/details/104631012

该题最大的难点，求解两圆相交的交点坐标

再结合此文计算几何---求解两圆相交的交点坐标

只看上文中的方法二，即可。

以下代码，求解两圆相交的交点坐标，是根据方法二，并对方法二结论，根据余弦定理进行优化而得。

提前说明，推导两圆相交的交点坐标，并写成代码，是比较耗时间的，建议读者，多次进行攻克。

代码同https://www.cnblogs.com/zdragon1104/p/12396167.html

#include <stdio.h>
#include <math.h>
#define maxn 65
#define eps 1e-8
double x[maxn],y[maxn],c[maxn],X[65*65*2],Y[65*65*2],r[maxn];
int tot,N,K;
double dis(double x,double y,double c,double X,double Y){
	return c*sqrt((X-x)*(X-x)+(Y-y)*(Y-y));
}
void cal(double x1,double y1,double r1,double x2,double y2,double r2){//计算两圆交点坐标
	double D;//A=a*a,H=h*h,D=d*d;
	double ad,h;//ad=a*d;
	D=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
	if(D==0)return;
	ad=(r1*r1+D-r2*r2)/2;//2*a*d=r1*r1+D-r2*r2
	h=D*r1*r1-ad*ad;
	if(h<0)return;//漏了此句的判定
	h=sqrt(h);
	tot++,X[tot]=x1+ad*(x2-x1)/D-(y2-y1)*h/D,Y[tot]=y1+ad*(y2-y1)/D+(x2-x1)*h/D;
	tot++,X[tot]=x1+ad*(x2-x1)/D+(y2-y1)*h/D,Y[tot]=y1+ad*(y2-y1)/D-(x2-x1)*h/D;
}
int judge(double t){
	int i,j,cnt;
	for(i=1;i<=N;i++)r[i]=t/c[i];
	tot=0;
	for(i=1;i<=N;i++){//计算出不同圆之间的交点坐标
		tot++,X[tot]=x[i],Y[tot]=y[i];//别忘了将圆心坐标放入交点坐标//此处错写成tot++,X[i]=x[i],Y[i]=y[i];
		for(j=i+1;j<=N;j++)
			cal(x[i],y[i],r[i],x[j],y[j],r[j]);
	}
	for(i=1;i<=tot;i++){
		cnt=0;
		for(j=1;j<=N;j++)
			if(dis(x[j],y[j],c[j],X[i],Y[i])<t+eps)cnt++;//浮点比大小无等于的情况，这是由浮点误差决定的。
		if(cnt>=K)return 1;
	}
	return 0;
}
int main(){
	double l,r,mid;
	int i;
	scanf("%d%d",&N,&K);
	for(i=1;i<=N;i++)scanf("%lf%lf%lf",&x[i],&y[i],&c[i]);
	l=0,r=1000010;
	while(l+eps<r){
		mid=(l+r)/2;
		if(judge(mid))r=mid;
		else l=mid;
	}
	printf("%.6lf\n",r);
	return 0;
}