https://www.luogu.org/problem/CF2C

题意:在平面上有三个没有公共部分的圆,求平面上一点使得到三个圆的切线的夹角相等。(若没答案满足条件,则不打印

思路:可用模拟退火算法来枚举答案点,可过,然而应该不是正解。先设一个最优解和初始步长,然后以当前步长不断搜索最优解更新答案,若答案不能更新,则步长减半再搜索,直到精度达到要求结束算法。

#include<cstdio>
#include<cmath>
const double EPS=1E-5; //控制精度
struct Point {
double x,y;
double r;
}P[3];
double Get(double x,double y,const Point b) { //求两点之间的距离
return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
}
double Check(double x,double y) { //估价函数
double t[3],delta[3],ret=0.0; //t为当前视角,delta表示误差值
for(int i=0;i<3;++i)
t[i]=Get(x,y,P[i])/P[i].r;
for(int i=0;i<3;++i) {
delta[i]=t[i]-t[(i+1)%3];
ret+=delta[i]*delta[i];
}
return ret; //返回误差的平方和
}
int main() {
bool mark;
double x=0.0,y=0.0;
for(int i=0;i<3;++i) {
scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].r);
x+=P[i].x/3;
y+=P[i].y/3; //设置近似最优解为三个圆圆心构成的三角形重心
}
for(double t=1.0,delta;t>EPS;) { //初始步长为1
mark=0; //搜索标记
delta=Check(x,y);
if(Check(x+t,y)<delta) { //搜索更优解
x+=t;
mark=1;
}
else if(Check(x-t,y)<delta) {
x-=t;
mark=1;
}
else if(Check(x,y+t)<delta) {
y+=t;
mark=1;
}
else if(Check(x,y-t)<delta) {
y-=t;
mark=1;
}
if(!mark) //搜索不到调整步长
t/=2;
}
if(fabs(Check(x,y))<EPS) //检查
printf("%.5lf %.5lf",x,y);
return 0;
}

最新文章

  1. WinForm下增加声音提示
  2. Linux模块机制浅析
  3. AMD and CMD are dead之KMDjs内核之分号
  4. getElementsByTagName() 方法
  5. 配置 Oracle 11g侦听器来使用SQL操作ST_Geometry(DLL路径问题)
  6. MYSQL 多行转多列
  7. Varnish介绍
  8. go语言常用函数:copy
  9. WPF绑定方式
  10. Python pexpect出现错误‘module have no attribute &quot;spawn&quot; 解决办法
  11. cvReleaseImage()函数说明
  12. ASP.NET MVC页面UI之多级数据选择UI(行业信息、专业信息、职位信息的选择)
  13. hdu1664 bfs+余数判重
  14. 使用mysqlbinlog对主库binlog进行同步
  15. RAS算法简单示例(Java版)
  16. PYTHON 格式字符串中的填充符
  17. 【js】把一个json对象转成想要的数组
  18. mybatis batch批量提交大量数据
  19. 分布式事务TransactionScope
  20. JQuery.validate 错误信息对话框

热门文章

  1. 20180827-Java网络编程
  2. (实战)多边形,梯形盒阴影css实现技巧
  3. flask的请求上下文request对象
  4. Oracle10g 64位 在Windows 2008 Server R2 中的安装 DBconsole无法启动
  5. React-Native 之 GD (二十一)APP 打包
  6. day63—JavaScript浏览器对象cookie
  7. MVC4:ajax Json 应用
  8. 《图解设计模式》读书笔记9-1 Flyweight模式
  9. 《图解设计模式》读书笔记8-3 STATE模式
  10. Model Inversion Attack Paper Indexpage