UVa (二分) 11627 Slalom

题意：

有宽度相同的水平的n个旗门，水平(纵坐标严格递增)滑行的最大速度为V_h(水平速度可以任意调节)。然后还有S双滑雪板，每双滑雪板的垂直速度一定。

然后求能通过的滑板鞋的最大速度。

分析：

显然，滑雪板的速度越小越容易通过所有的旗门。然后二分找出这个能通过旗门的最大值，最后在滑雪板里面找出这个范围的最大值。

如何判断某个速度可以通过所有的旗门：

第一个旗门处起点可以是任意的，到达第二个旗门的垂直高度时有一个范围，然后和第二个旗门的宽度的范围求交集。如果为∅，则不能通过。否则，继续求到达下一个高度的范围，再和第三个旗门的范围求交集。

在敲代码的过程中，judge函数WA掉了，后来看的别人的写法过的。浮点运算尽是坑啊，Orz

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn1 =  + ;

 const int maxn2 =  + ;

 int w, vx, n;

 int x[maxn1], y[maxn1], s[maxn2];

 bool judge(int vy)

 {

     int i,j;

     double x1,x2;

     x1=x[];

     x2=x[] + w;

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

     {

         double d = vx*1.0*(y[i] - y[i-]) / vy;

         x1 -= d,x2 += d;

         x1 = max(x1, x[i]*1.0);

         x2 = min(x2, (x[i] + w)*1.0);

         if(x1 - x2>1e-)

         {

             return false;

         }

     }

     return true;

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("11627in.txt", "r", stdin);

     #endif

     int T, m, i;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d%d", &w, &vx, &n);

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

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

         int L = , R = maxn2;

         while(L < R)

         {

             int mid = L + (R - L + ) / ;

             if(judge(mid))    L = mid;

             else    R = mid - ;

         }

         int ans = ;

         scanf("%d", &m);

         for(i = ; i < m; ++i)

         {

             int x;

             scanf("%d", &x);

             if(x <= L)

                 ans = max(ans, x);

         }

         if(ans)

             printf("%d\n", ans);

         else

             puts("IMPOSSIBLE");

     }

     return ;

 }

代码君

巴特西

UVa (二分) 11627 Slalom

最新文章

热门文章