洛谷P3114 Stampede S

题目描述

Farmer John's N cows (1 <= N <= 50,000) appear to be stampeding along the road at the front of FJ's farm, but they are actually just running in a foot race to see which cow is the fastest.

农夫约翰的N头奶牛（1头<=N<=50000头）似乎在FJ农场前面的道路上奔跑，但实际上他们只是在赛跑，看哪头奶牛跑得最快。

Viewed from above, each cow is represented by a unit-length horizontal line segment, specified by the coordinates of its left corner point at time t=0. For example, (-3,6) would specify a cow who at time t=0 is represented by the segment from (-3,6) to (-2,6). Each cow is moving to the right (in the +x direction) at a certain rate, specified by the integer amount of time it takes her to move 1 unit to the right.

从上面看，每个cow由单位长度的水平线段表示，由t=0时其左角点的坐标指定。例如，（-3,6）将指定在t=0时由从（-3,6）到（-2,6）的段表示的奶牛。每头母牛都以一定的速率向右移动（在+x方向上），这是由母牛向右移动1个单位所需的整数时间指定的。

FJ is not particularly thrilled that his cows are outside running instead of in the barn producing milk. He plans to admonish them with a stern lecture after the race ends. In order to determine which of his cows are participating in the race,

FJ并不特别兴奋，因为他的奶牛在外面跑，而不是在谷仓里产奶。他计划在比赛结束后严厉地训诫他们。为了确定他的哪些奶牛参加了比赛，

FJ situates himself at (0,0) and looks along a ray extending in the +y direction. As the race unfolds, FJ sees a cow if she is ever the first cow visible along this ray. That is, a cow might not be visible if another cow is "in front" of her during the entire time she crosses FJ's line of sight.

FJ将自己定位在（0,0）处，并沿+y方向延伸的光线进行观察。随着比赛的展开，FJ看到了一头奶牛，如果她是这条射线上第一头可见的奶牛的话。也就是说，如果在穿过FJ视线的整个过程中，另一头牛“在”她的前面，那么它可能看不见。

Please compute the number of cows FJ can see during the entire race.

请计算FJ在整个比赛中能看到的奶牛数量。

DJ站在原点上向y轴正半轴看，然后有一群奶牛从他眼前飞过。这些奶牛初始都在第二象限，尾巴在(Xi,Yi)，头在(Xi+1,Yi)，每Ci秒向右走一个单位。 DJ能看见一匹奶牛当且仅当它身体任意某部位x坐标为0时，没有其它y坐标小于此奶牛的奶牛身体某部位x坐标为0。 问DJ能看见多少奶牛？

输入格式

输入：（stampede.in文件）
输入的第一行包含N。以下N行中的每一行描述了一个具有三个整数x y r的cow，对应于一个cow，其左端点在时间t=0时位于（x，y），每r个时间单位以1单位距离的连续速度向右移动。x的值在-1000范围内-1，y的值在范围1内。。1000000（每个cow都不同，以防止任何可能的碰撞），并且r的值在1.的范围内。。1,000,000.

输出格式

输出：（文件stampede.out）
单个整数，指定FJ在测试过程中可以看到的奶牛数量
整个比赛（从t=0开始）。

输入输出样例

输入 #1复制

3 
-2 1 3 
-3 2 3 
-5 100 1

输出 #1复制

2

上代码：

#include<bits/stdc++.h>
#define rd(n) scanf("%lld",&n);
#define F(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
const int N=4e5+10;
long long n,p,v,x;
long long st[N],ed[N],t[N];
int c[N],d[N],y[N];
int main() {
    rd(n)
    F(i,1,n) {
        rd(x)rd(y[i])rd(v)
        x++;
        x=-x;//将坐标转化为距离 
        st[i]=x*v;
        ed[i]=st[i]+v-1;
        t[++p]=st[i],t[++p]=ed[i];
        t[++p]=ed[i]+1;//左闭右开
    }
    memset(c,0x3f,sizeof(c));
    sort(t+1,t+p+1);//先排序再离散化 
    long long cnt=unique(t+1,t+p+1)-t-1;
    F(i,1,n) {
        st[i]=lower_bound(t+1,t+cnt+1,st[i])-t;//离散化 
        ed[i]=lower_bound(t+1,t+cnt+1,ed[i])-t;
        F(j,st[i],ed[i]){//暴力覆盖 
            if(c[j]>y[i]){//如果覆盖这一段时间的奶牛的 y 值大于现在的奶牛，就更新 
                c[j]=y[i];//c 模拟时间轴上奶牛的 y 值 
                d[j]=i;//d 记录时间轴上的奶牛编号 
            }
        }
    }
    int ans=0;
    F(i,1,n) {
        F(j,st[i],ed[i]) {
            if(d[j]==i){
                ans++;//如果第 i 头奶牛经过 y 轴的时间内能被看到，答案+1 
                break;
            }
        }
    }
    printf("%d",ans);
    return 0;
}