HDU 4816 Bathysphere （2013长春现场赛D题）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4816

2013长春区域赛的D题。

很简单的几何题，就是给了一条折线。 然后一个矩形窗去截取一部分，求最大面积。

现场跪在这题，最后时刻TLE到死，用的每一小段去三分，时间复杂度是O(n log n) , 感觉数据也不至于超时。

卧槽！！！！代码拷回来，今天在HDU一交，一模一样的代码AC了，加输入外挂6s多，不加也8s多，都可AC，呵呵·····（估计HDU时限放宽了！！！）

现场赛卡三分太SXBK了，我艹！！！！ 好好的一个现场赛绝杀错过了。

以下是现场赛源码，在HDU顺利AC！ 现场TLE到死！

其实O(n)也可以搞，因为是三分的是一个二次函数，求对称轴就可以了。现场没有想到这个优化，等下简单修改成O(n)代码。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 #include <map>

 #include <set>

 #include <vector>

 #include <string>

 #include <math.h>

 using namespace std;

 const int MAXN = ;

 int x[MAXN],y[MAXN];

 int d;

 int n;

 int L;

 int nowx ;

 int nextx;

 int r1,l2;

 const double eps = 1e-;

 double solve()

 {

     double left = nowx,right = nextx;

     double ret1,ret2;

     for(int cc = ;cc <= ;cc++)

     {

         double mid = (left + right)/;

         double midmid = (mid + right)/;

         double h1 = y[r1] + (double)(y[r1-] - y[r1]) * (mid  - x[r1])/(x[r1-] - x[r1]);

         double h2 = y[l2] + (double)(y[l2+] - y[l2])*(mid + *d - x[l2])/(x[l2 + ] - x[l2]);

         ret1 = (double)(x[r1] - mid)*(h1 + y[r1])/ + (double)(mid + *d - x[l2])*(h2 + y[l2])/;

          h1 = y[r1] + (double)(y[r1-] - y[r1]) * (midmid  - x[r1])/(x[r1-] - x[r1]);

          h2 = y[l2] + (double)(y[l2+] - y[l2])*(midmid + *d - x[l2])/(x[l2 + ] - x[l2]);

         ret2 = (double)(x[r1] - midmid)*(h1 + y[r1])/ + (double)(midmid + *d - x[l2])*(h2 + y[l2])/;

         if(ret1 < ret2)

             left = mid+eps;

         else right = midmid-eps;

     }

     return ret1;

 }

 int input()

 {

     char ch;

     ch = getchar();

     while(ch < '' || ch >'')

     {

         ch = getchar();

     }

     int ret = ;

     while(ch >= '' && ch <= '')

     {

         ret *= ;

         ret += ch -'';

         ch = getchar();

     }

     return ret;

 }

 int main()

 {

     //freopen("D.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&L);

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

         {

             //x[i] = input();

             //y[i] = input();

             scanf("%d%d",&x[i],&y[i]);

         }

             //scanf("%d%d",&x[i],&y[i]);

         scanf("%d",&d);

         double ans = ;

          r1 = ;

          l2 = ;

         double tmp = ;

         while(l2 < n && x[l2+] < *d)l2++;

         for(int i = r1;i < l2;i++)

         {

             tmp += (double)(x[i+] - x[i])*(y[i] + y[i+])/;

         }

         if(l2  == )

         {

             tmp -= (double)(x[] - x[])*(y[] + y[])/;

         }

         x[n+] = x[n];

         y[n+] = y[n];

         nowx = ;

         //printf("%d %d\n",r1,l2);

         while(l2 < n && r1 <= n)

         {

             int p1 = x[r1];

             int p2 = x[l2 + ] - *d;

             if(p1 < p2)

                 nextx = p1;

             else nextx = p2;

             nextx = min(L- *d,nextx);

             //printf("%d %d\n",nowx,nextx);

             ans = max(ans,tmp + solve());

             if(p1 < p2)

             {

                 nowx = p1;

                 if(r1 < n)tmp -= (double)(x[r1+] - x[r1])*(y[r1+] + y[r1] )/;

                 r1++;

             }

             else

             {

                 nowx = p2;

                 tmp += (double)(x[l2+] - x[l2])*(y[l2+] + y[l2])/;

                 l2++;

             }

         }

         printf("%.3lf\n",ans//d);

     }

     return ;

 }

改成了O(n)的解法。

因为三分的那个函数是二次函数。

找最大值，只要找两个端点和对称轴处就足够了！

还是太弱，现场没有想到这个优化，改起来很容易的。

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 #include <map>

 #include <set>

 #include <vector>

 #include <string>

 #include <math.h>

 using namespace std;

 const int MAXN = ;

 int x[MAXN],y[MAXN];

 int d;

 int n;

 int L;

 int nowx ;

 int nextx;

 int r1,l2;

 const double eps = 1e-;

 double solve()

 {

     double left = nowx,right = nextx;

     //求出二次函数的a,b,c系数

     double tmp11 = x[r1];

     double tmp12 = -;

     double tmp13 = (double)y[r1] - (double)x[r1]*(y[r1-] - y[r1])/(x[r1-] - x[r1])/;

     double tmp14 = (double)(y[r1-] - y[r1])/(x[r1-] - x[r1])/;

     double tmp21 = *d - x[l2];

     double tmp22 = ;

     double tmp23 = y[l2] + (double)(*d - x[l2])*(y[l2+] - y[l2])/(x[l2+] - x[l2])/;

     double tmp24 = (double)(y[l2+] - y[l2])/(x[l2+] - x[l2])/;

     //函数Y = (tmp11 + tmp12 * x)*(tmp13 + tmp14 * x) + (tmp21 + tmp22 * x)*(tmp23 + tmp24*x)

     double a = tmp12 * tmp14 + tmp22 * tmp24;

     double b = tmp11 * tmp14 + tmp12 * tmp13 + tmp21 * tmp24 + tmp22 * tmp23;

     double c = tmp11 * tmp13 + tmp21 * tmp23;

     double x0 = -b /(*a);//对称轴

     double ret = max(a*left*left + b*left + c,a*right *right + b * right + c);

     if(x0 >= left && x0 <= right)

         ret = max(ret,a * x0 * x0 + b*x0 + c);

     return ret;

     /*

     double ret1,ret2;

     for(int cc = 0;cc <= 30;cc++)

     {

         double mid = (left + right)/2;

         double midmid = (mid + right)/2;

         double h1 = y[r1] + (double)(y[r1-1] - y[r1]) * (mid  - x[r1])/(x[r1-1] - x[r1]);

         double h2 = y[l2] + (double)(y[l2+1] - y[l2])*(mid + 2*d - x[l2])/(x[l2 + 1] - x[l2]);

         ret1 = (double)(x[r1] - mid)*(h1 + y[r1])/2 + (double)(mid + 2*d - x[l2])*(h2 + y[l2])/2;

          h1 = y[r1] + (double)(y[r1-1] - y[r1]) * (midmid  - x[r1])/(x[r1-1] - x[r1]);

          h2 = y[l2] + (double)(y[l2+1] - y[l2])*(midmid + 2*d - x[l2])/(x[l2 + 1] - x[l2]);

         ret2 = (double)(x[r1] - midmid)*(h1 + y[r1])/2 + (double)(midmid + 2*d - x[l2])*(h2 + y[l2])/2;

         if(ret1 < ret2)

             left = mid+eps;

         else right = midmid-eps;

     }

     return ret1;

     */

 }

 int input()

 {

     char ch;

     ch = getchar();

     while(ch < '' || ch >'')

     {

         ch = getchar();

     }

     int ret = ;

     while(ch >= '' && ch <= '')

     {

         ret *= ;

         ret += ch -'';

         ch = getchar();

     }

     return ret;

 }

 int main()

 {

     //freopen("D.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&L);

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

         {

             //x[i] = input();

             //y[i] = input();

             scanf("%d%d",&x[i],&y[i]);

         }

             //scanf("%d%d",&x[i],&y[i]);

         scanf("%d",&d);

         double ans = ;

          r1 = ;

          l2 = ;

         double tmp = ;

         while(l2 < n && x[l2+] < *d)l2++;

         for(int i = r1;i < l2;i++)

         {

             tmp += (double)(x[i+] - x[i])*(y[i] + y[i+])/;

         }

         if(l2  == )

         {

             tmp -= (double)(x[] - x[])*(y[] + y[])/;

         }

         x[n+] = x[n];

         y[n+] = y[n];

         nowx = ;

         //printf("%d %d\n",r1,l2);

         while(l2 < n && r1 <= n)

         {

             int p1 = x[r1];

             int p2 = x[l2 + ] - *d;

             if(p1 < p2)

                 nextx = p1;

             else nextx = p2;

             nextx = min(L- *d,nextx);

             //printf("%d %d\n",nowx,nextx);

             ans = max(ans,tmp + solve());

             if(p1 < p2)

             {

                 nowx = p1;

                 if(r1 < n)tmp -= (double)(x[r1+] - x[r1])*(y[r1+] + y[r1] )/;

                 r1++;

             }

             else

             {

                 nowx = p2;

                 tmp += (double)(x[l2+] - x[l2])*(y[l2+] + y[l2])/;

                 l2++;

             }

         }

         printf("%.3lf\n",ans//d);

     }

     return ;

 }