AtCoder Beginner Contest 130 F Minimum Bounding Box 三分法求极值（WA）

题意：给n个点的起始坐标以及他们的行走方向，每一单位时间每个点往它的方向移动一单位。问最小能包围所有点的矩形。

解法：看到题目求极值，想了想好像可以用三分法求极值，虽然我也不能证明面积是个单峰函数。

尝试交了一发结果73组数据WA了1组数据，看起来似乎三分法是对的，但是至今还没找到哪个细节错了qwq，先记录下来。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 int n,m,x[N],y[N];

 char d[N][];

 double xmax,xmin,ymax,ymin;

 void chg(double x,double y) {

     xmax=max(xmax,x); xmin=min(xmin,x);

     ymax=max(ymax,y); ymin=min(ymin,y);

 }

 double calc(double t) {

     xmax=-INF,xmin=INF,ymax=-INF,ymin=INF;

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

         if (d[i][]=='R') chg(x[i]+t,y[i]);

         if (d[i][]=='L') chg(x[i]-t,y[i]);

         if (d[i][]=='U') chg(x[i],y[i]+t);

         if (d[i][]=='D') chg(x[i],y[i]-t);

     }

     return (double)(xmax-xmin)*(ymax-ymin);

 }

 int main()

 {

     cin>>n;

     for (int i=;i<=n;i++) scanf("%d%d%s",&x[i],&y[i],d[i]);

     double l=,r=1e8, lm, rm;

     while(r-l>eps) {

         lm = l+(r-l)/;

         rm = lm+(r-lm)/;

         if(calc(lm) < calc(rm)) r = rm;

         else if(calc(lm) == calc(rm)) r=rm, l=lm;

         else l = lm;

     }

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

     return ;

 }