HOJ 2245 浮游三角胞（数学啊 ）

题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2245

Time Limit: 500 MS Memory Limit: 50000 K Total Submit: 129(38 users) Total Accepted: 66(34 users) Rating: Special Judge: No

Description

如图所示，Zoidtrip是一个休闲向小游戏…… 玩家需要操纵一个以斜向下四十五度速度v不停前进的三角胞，不停地避开水平障碍物，每次点击屏幕可以变换行进方向。[可以将斜向左（右）45°变换为斜向右(左)45°] 现在，有n层障碍物，第i层障碍物可以从横坐标l[i]~r[i]的范围内穿过去（包括l[i]与r[i]），第i层障碍物与第i-1层障碍物之间的距离为d[i]。 请问，假定在可以无限变换方向的条件下，最多可以前进至第几层? 我们规定玩家出生位置为第0层、横坐标为0的地方。 你可以在任意实数时刻进行方向变换。

Input

多组测试数据。 每组测试数据第一行为两个正整数 n和v。 接下来n行，每行3个整数l[i] , r[i] , d[i]。 ( N <= 2000000，0 <= 所有数据 < 2^31 )

Output

对于每组数据，输出一行，包含一个整数，代表最多前进至的层数。

Sample Input

3 7 1 3 1 4 10 5 8 10 1 4 1 1 1 1 2 5 10 1 1 1 3 5 2

Sample Output

2 4

Hint

“第i层障碍物与第i-1层障碍物之间的距离为d[i]” 因此d[1]是第一层和第零层的距离。 样例1解释如下： 我们可以出生位置向右下移动至第一层坐标为1的地方。 接下来可以继续一直向右下移动至第二层坐标为6的地方。 但无论如何也无法移动至第三层的8~10之间。 样例2说明如下： (0,0)->(1,1)->(2,2)->(3,1)->(4,3) 因此到达第四层。

Source

哈尔滨理工大学第五届ACM程序设计竞赛

PS:

把 三角胞在每一层能走到的且满足能避开障碍物的最左和最右的距离找出来!

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define maxn 2000047
LL l[maxn], r[maxn], d[maxn];

int main()
{
    LL n, v;
    while(scanf("%lld%lld",&n,&v)!=EOF)
    {
        LL L = 0,R = 0;
        int ans = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%lld%lld%lld",&l[i],&r[i],&d[i]);
        }
        for(int i = 0; i < n; i++)
        {
            if(l[i] > r[i])
            {
                LL t = r[i];
                r[i] = l[i];
                l[i] = t;
            }
            L-=d[i];
            R+=d[i];
            L = max(l[i],L);
            R = min(r[i],R);
            if(L > R)
            {
                break;
            }
            ans++;
        }
        if(v == 0)
            ans = 0;
        printf("%d\n",ans);
    }
    return 0;
}

HOJ 2245 浮游三角胞（数学啊 ）

原文：http://blog.csdn.net/u012860063/article/details/44784163