ZEBRA - The Zebra Crossing

no tags 

Have you ever wondered why people collide with each other at pedestrian crossings? The reasons are probably difficult to analyse from a scientific point of view, but we can hazard a guess. A part of the problem seems to be that the statistical pedestrian, when faced with a red light, will either cross at once (this category of pedestrians doesn't really interest us, since they tend to collide with cars rather than with each other), or will stop dead and stand still until the light changes. Only when the light turns green does he begin to act rationally and heads for his destination using the shortest possible path. Since this usually involves crossing the road slightly on the bias, he will inevitably bump into someone going across and heading another way.

One day, while you are approaching the traffic lights you usually cross at, you begin to wonder how many other people you could possibly collide with if you really wanted. All the people are standing at different points on the same side of the street as you are. From past observations you can predict the exact angle and speed at which individual pedestrians are going to cross. You can decide at which point along the side of the street you will wait for the green light (any real coordinate other than a place where some other pedestrian is already standing) and at what angle and at what speed you intend to cross. There is an upper bound on the speed you may cross at.

Assume that once the light turns green, all pedestrians start moving along straight lines, at constant speed, and that collisions, however painful they may be, have no effect on their further progress. Since you wouldn't like to arouse anyone's suspicions, you also have to cross in accordance with these rules. A collision only occurs if at a given moment of time you have exactly the same x and y coordinates as some other pedestrian.


Input starts with a single integer t, the number of test cases (t<=100). t test cases follow.

Each test case begins with a line containing three integers n w v, denoting the number of people other than you who wish to cross the street, the width of the street expressed in meters, and the maximum speed you can walk at given in meters per second, respectively (1<=n<=10000, 1<=w<=100, 1<=v<=10000). Each of the next n lines contains three integers xi ti ai, which describe the starting position of the i-th pedestrian measured in meters, the time (in seconds) he takes to cross the street, and the angle at which he is walking with respect to the line normal to the sides of the street, expressed in 1/60 parts of a degree (-10000<=xi<=10000, 1<=ti<=10000, -5000<=ai<=5000).

Illustration of problem input


For each test case output a single integer -- the maximum number of people you can collide with by the time you reach the opposite side of the street.


5 20 2
-20 10 2700
20 10 -2700
-5 1 4000
-4 1 4000
5 1 -4000


(In the example, due to the imposed speed limit, it is only possible to collide with the first two pedestrians while crossing the street, at the last possible moment.)

hide comments
bigbag: 2019-05-18 09:52:40

We can choose any real angle, or only angle from the range [-5000; 5000] (in 1/60 parts of a degree)?

archie155: 2019-05-05 22:12:02

Is after crossing zebra person stay in the end for a long time?

ALOK KUMAR: 2015-05-07 18:26:25

@liv_curious : Yes my friend. :)

Last edit: 2015-05-07 18:35:41
liv_curious: 2014-12-15 09:17:55

Are all input integers?

Last edit: 2014-12-15 11:25:50

Added by:adrian
Time limit:17s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:DASM Programming League 2004, problemset 7