P3114 [USACO15JAN]踩踏Stampede

    • 79通过
    • 262提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2015 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    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.

    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 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.

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

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

    输入输出格式

    输入格式:

    INPUT: (file stampede.in)

    The first line of the input contains N. Each of the following N lines describes a cow with three integers x y r, corresponding to a cow whose left endpoint is at (x,y) at time t=0, moving to the right at a continuous speed of 1 unit of distance every r units of time. The value of x is in the range -1000..-1, the value of y is in the range 1..1,000,000 (and distinct for every cow, to prevent any possible collisions), and the value of r is in the range 1..1,000,000.

    输出格式:

    OUTPUT: (file stampede.out)

    A single integer, specifying the number of cows FJ can see during the

    entire race (from t=0 onward).

    输入输出样例

    输入样例#1: 复制
    3 
    -2 1 3 
    -3 2 3 
    -5 100 1 
    
    输出样例#1: 复制
    2 
    

    说明

    SOLUTION NOTES:

    FJ can see cows 1 and 2 but not cow 3.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。