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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 const int INF=0x3f3f3f3f;
 5 const double eps=1e-16;
 6 int n,m,x[N],y[N];
 7 char d[N][3];
 8 
 9 double xmax,xmin,ymax,ymin;
10 void chg(double x,double y) {
11     xmax=max(xmax,x); xmin=min(xmin,x);
12     ymax=max(ymax,y); ymin=min(ymin,y);
13 }
14 
15 double calc(double t) {
16     xmax=-INF,xmin=INF,ymax=-INF,ymin=INF;
17     for (int i=1;i<=n;i++) {
18         if (d[i][0]==‘R‘) chg(x[i]+t,y[i]);
19         if (d[i][0]==‘L‘) chg(x[i]-t,y[i]);
20         if (d[i][0]==‘U‘) chg(x[i],y[i]+t);
21         if (d[i][0]==‘D‘) chg(x[i],y[i]-t);
22     }
23     return (double)(xmax-xmin)*(ymax-ymin);
24 }
25 
26 int main()
27 {
28     cin>>n;
29     for (int i=1;i<=n;i++) scanf("%d%d%s",&x[i],&y[i],d[i]);
30     double l=0,r=1e8, lm, rm;
31     while(r-l>eps) {
32         lm = l+(r-l)/2;
33         rm = lm+(r-lm)/2;
34         if(calc(lm) < calc(rm)) r = rm;
35         else if(calc(lm) == calc(rm)) r=rm, l=lm;
36         else l = lm;
37     }
38     printf("%.10lf\n",calc(l));
39     return 0;
40 }