CodeForces - 1059D——二分/三分

题目

简单的说，就是作一个圆包含所有的点且与x轴相切，求圆的最小半径

方法一

分析：求最小，对半径而言肯定满足单调性，很容易想到二分。我们二分半径，然后由于固定了与X轴相切，我们对于每一个点，就可以算出这个点在圆上的时候圆与x轴相交的距离（其实就是圆心的x轴的范围）。然后对每个点都可以求一个圆心的横坐标区间，如果所有的区间有相交区域，则该半径满足条件，否则不满足。

代码：

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn =  + ;

 const double esp = 1e-;

 struct Piont

 {

     double x, y;

 }p[maxn];

 int n;

 bool judge(double r)

 {

     double ml = -1e15, mr = 1e15;

     for (int i = ; i < n; i++)

     {

         if (p[i].y >  * r)  return false;        //大于2倍半径的，肯定不行

         double tmp = sqrt( * p[i].y * r - p[i].y * p[i].y);

         if (p[i].x - tmp > ml)  ml = p[i].x - tmp;

         if (p[i].x + tmp < mr)  mr = p[i].x + tmp;

     }

     return ml <= mr;                //所有区间必须要有交点

 }

 int main()

 {

     while (scanf("%d", &n) == )

     {

         int flag1 = , flag2 = ;

         for (int i = ; i < n; i++)

         {

             scanf("%lf%lf", &p[i].x, &p[i].y);

             if (p[i].y > )  flag1 = ;

             if (p[i].y < )  flag2 = ;

             if (p[i].y < )  p[i].y = -p[i].y;

         }

         if (flag1 && flag2)

         {

             printf("-1\n");

             continue;

         }

         double l = , r = 1e15, mid;        //直接枚举圆的半径，范围大约是1e7的平方

         int cnt = ;                //二分100次精度足够了

         while (cnt--)                //这里写成(r - l) < esp陷入了死循环。。。

         {

              mid = (r + l) / 2.0;

             if (judge(mid)) r = mid;

             else  l = mid;

         }

         printf("%.10lf\n", r);

     }

     return ;

 }

方法二

分析：设圆心的横坐标为x,由勾股定理有(x-x0)² + (r-y)² = r²,得r = (x-x0)²/2y + y/2,所以R = max(r1,r2,,,rn),也就是说x确定时，R也随之确定。

我们又发现，对于答案所在得X，在它左右走R都会单调递增，形成像山谷那样得形状，那么直接三分X直接找到谷底即可。

具体的三分做法如下：

设答案所在区间为(l,r),dx = (r-l)/3,则mr = r+dx,ml = l-dx。设cal(x)是计算圆心在x时r的值，若cal(ml) < cal(mr),有两种情况，异侧如①，同侧如③，所以将r更新为mr,而不是更新为ml,同理，若cal(ml) > cal(mr),则将l更新为ml。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn =  + ;

 const double esp = 1e-;

 struct Piont

 {

     double x, y;

 }p[maxn];

 int n;

 double cal(double x)

 {

     double r = ;

     for (int i = ; i < n; i++)

         r = max(r, p[i].y / 2.0 + (x - p[i].x) * (x - p[i].x) / p[i].y / 2.0);

     return r;

 }

 int main()

 {

     while (scanf("%d",&n) == )

     {

         int flag1 = , flag2 = ;

         for (int i = ; i < n; i++)

         {

             scanf("%lf%lf", &p[i].x, &p[i].y);

             if (p[i].y > )  flag1 = ;

             if (p[i].y < )  flag2 = ;

             if (p[i].y < )  p[i].y = -p[i].y;

         }

         if (flag1 && flag2)

         {

             printf("-1\n");

             continue;

         }

         //R=y1/2 + (x-x1)^2/2y,x是圆心坐标，R关于x先减后增

         double l = -1e7, r = 1e7,dx;        //枚举圆的半径,也就是枚举圆心横坐标

         while (r - l > esp)                    //也可改成cnt<100

         {

             dx = (r - l) / 3.0;

             double lx = l + dx, rx = r - dx;

             if (cal(lx) - cal(rx) < )  r = rx;

             else  l = lx;

         }

         int tmp = cal(r);

         printf("%.6lf\n", cal(r));

     }

     return ;

 }

参考链接：

https://blog.csdn.net/lzc504603913/article/details/82949923

https://blog.csdn.net/qq_37555704/article/details/82949337

http://www.cnblogs.com/sdfzhsz/p/9748360.html

https://blog.csdn.net/winter2121/article/details/82949159?tdsourcetag=s_pctim_aiomsg

巴特西

CodeForces - 1059D——二分/三分

最新文章

热门文章