【转】【计算几何转化模拟退火】求一个点，使得该点到三个圆的视角范围尽可能接近

转自：http://blog.csdn.net/snowy_smile/article/details/50131317

The Olympic Games in Bercouver are in full swing now. Here everyone has their own objectives: sportsmen compete for medals, and sport commentators compete for more convenient positions to give a running commentary. Today the main sport events take place at three round stadiums, and the commentator's objective is to choose the best point of observation, that is to say the point from where all the three stadiums can be observed. As all the sport competitions are of the same importance, the stadiums should be observed at the same angle. If the number of points meeting the conditions is more than one, the point with the maximum angle of observation is prefered.

Would you, please, help the famous Berland commentator G. Berniev to find the best point of observation. It should be noted, that the stadiums do not hide each other, the commentator can easily see one stadium through the other.

Input

The input data consists of three lines, each of them describes the position of one stadium. The lines have the format x, y, r, where (x, y) are the coordinates of the stadium's center ( - 103 ≤ x, y ≤ 103), and r (1 ≤ r ≤ 103) is its radius. All the numbers in the input data are integer, stadiums do not have common points, and their centers are not on the same line.

Output

Print the coordinates of the required point with five digits after the decimal point. If there is no answer meeting the conditions, the program shouldn't print anything. The output data should be left blank.

Sample test(s)

input

0 0 10
60 0 10
30 30 10

output

30.00000 0.00000

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<ctype.h>
  4 #include<math.h>
  5 #include<iostream>
  6 #include<string>
  7 #include<set>
  8 #include<map>
  9 #include<vector>
 10 #include<queue>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<time.h>
 14 using namespace std;
 15 void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
 16 #define MS(x,y) memset(x,y,sizeof(x))
 17 #define MC(x,y) memcpy(x,y,sizeof(x))
 18 #define MP(x,y) make_pair(x,y)
 19 #define ls o<<1
 20 #define rs o<<1|1
 21 typedef long long LL;
 22 typedef unsigned long long UL;
 23 typedef unsigned int UI;
 24 template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
 25 template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
 26 const int N=0,M=0,Z=1e9+7,ms63=1061109567;
 27 struct Circle
 28 {
 29     double x,y,r;
 30 }c[3];
 31 double ang[3];
 32 const int dy[4]={-1,0,0,1};
 33 const int dx[4]={0,-1,1,0};
 34 double K(double x)
 35 {
 36     return x*x;
 37 }
 38 double Dis(double x,double y,double xx,double yy)
 39 {
 40     return sqrt(K(x-xx)+K(y-yy));
 41 }
 42 double Val(double x,double y)
 43 {
 44     for(int i=0;i<3;++i)ang[i]=Dis(x,y,c[i].x,c[i].y)/c[i].r;
 45     double val=0;
 46     for(int i=0;i<3;++i)val+=K(ang[i]-ang[(i+1)%3]);
 47     return val;
 48 }
 49 int main()
 50 {
 51     double x=0,y=0;
 52     for(int i=0;i<3;++i)
 53     {
 54         scanf("%lf%lf%lf",&c[i].x,&c[i].y,&c[i].r);
 55         x+=c[i].x/3;y+=c[i].y/3;
 56     }
 57     double err=Val(x,y);
 58     double step=1;
 59     for(int tim=1;tim<=1e5;++tim)
 60     {
 61         bool flag=0;
 62         double X,Y;
 63         for(int i=0;i<4;++i)
 64         {
 65             double xx=x+dx[i]*step,yy=y+dy[i]*step;
 66             double val=Val(xx,yy);
 67             if(val<err)
 68             {
 69                 err=val;
 70                 flag=1;
 71                 X=xx;Y=yy;
 72             }
 73         }
 74         if(flag){x=X;y=Y;}
 75         else step/=2;
 76     }
 77     if(err<1e-6)printf("%.5f %.5f
",x,y);
 78     return 0;
 79 }
 80 /*
 81 【trick&&吐槽】
 82 啦啦啦！
 83 
 84 【题意】
 85 给你三个圆，让你找到一个点，使得从这个点出发，看三个圆的视角范围的角度都一样。
 86 如果有多个满足要求的点，我们希望找到一个点，使得这个视角范围的角度尽可能大。
 87 （如果无解就不输出）
 88 
 89 【类型】
 90 计算几何公式求解or模拟退火
 91 
 92 【分析】
 93 这题可以直接解方程，用计算几何的方法做。
 94 然而最好的，最值得学习有推广价值的算法还是——模拟退火。
 95 
 96 什么是模拟退火呢？以后我们可以再慢慢具体学习。（才不是因为我现在不会啦~  T_T ）
 97 按照这道题的学习，大体上是这样做——
 98 bas，设计估价函数
 99 1，初始找一个近似最优解，
100 2，然后在最优解的四周寻求更优解。这里要保证步长不要太小，否则可能陷入局部最优解。
101 3，重复步骤2，适当调整步长，继续寻找最优解，直到达到精度要求。
102 
103 在这道题上——
104 估价函数要先求出（距离/半径），这个数值和视角大小有相应的一一对应关系。
105     然后求出三个圆pair的（距离/半径）的差值的平方和，作为估价函数。
106     这个值越小，越接近零，显然对于三个圆的视角越接近。
107 1是重心
108 2初始为1，找得到更优就继续走。找不到更优就步长缩半
109 3直到一定的次数或一定的精度
110 然后这道题就做完啦！做完啦！做完啦！
111 以后再来加深学习模拟退火哦~~！
112 
113 ====================================================================
114 当然这题有解方程做法啦。因为满足要求的点数其实一筛就没几个了哦~以后再补！
115 
116 【时间复杂度&&优化】
117 O（模拟退火次数）
118 
119 */

【转】【计算几何 转化 模拟退火】求一个点，使得该点到三个圆的视角范围尽可能接近

【转】【计算几何转化模拟退火】求一个点，使得该点到三个圆的视角范围尽可能接近