Codeforces-2C Commentator problem(随机算法)

题目链接

题意：给出三个圆，求找到一个点使得该点到三个圆的视角（过圆外一点做圆的两条切线，夹角就是视角）相等，求这个点的坐标。

思路：先找到三个点的重心，然后再无限逼近正确答案，这里用到了随机算法。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <set>
#include <stack>
#include <cmath>
#define pf(x)  ((x)*(x))
using namespace std;
const int N = 1000 + 2;
double x[4], y[4], r[4];
double dx, dy;
double Fun(double dx, double dy)
{
    double ap[4];
    for (int i = 0;i < 3; i++)
    {
        ap[i] = sqrt( pf( x[i] - dx ) + pf( y[i] - dy ) ) / r[i];
    }
    double res = 0.0;
    for (int i = 0; i < 3; i++)
    {
        res += pf(  ap[i] - ap[ (i + 1)  % 3]  );
    }
    return res;
}

int main()
{
   dx = dy = 0.0;
   for (int i = 0; i < 3; i++)
   {
       scanf("%lf%lf%lf", &x[i], &y[i], &r[i] );
       dx += x[i] / 3;
       dy += y[i] / 3;
   }
   double i = 1.0;
   while (i > 1e-5)
   {
        if ( Fun(dx + i, dy) < Fun(dx, dy) ) dx += i;
        else if ( Fun(dx - i, dy) < Fun(dx, dy) ) dx -= i;
        else if ( Fun(dx, dy + i) < Fun(dx, dy) ) dy += i;
        else if ( Fun(dx, dy - i ) < Fun(dx, dy) ) dy -= i;
        else i *= 0.75;
   }
   if ( Fun(dx, dy) < 1e-5 ) printf("%.5lf %.5lf\n", dx, dy );
   return 0;
}