### PROBLEM LINK:

**Setter-** Ashesh Vidyut

**Tester-** Misha Chorniy

**Editorialist-** Abhishek Pandey

### DIFFICULTY:

EASY

### PRE-REQUISITES:

Math, Implementation, Dealing with floating points & similar etc.

Several interpretations about domain and category of this problem are possible. One may see it as one of Physics numerical of type Kinematics, others may see it as Vectors in Maths, while some may compare it to Geometry by using 2-D graph and due to the fact that this concept of distance being >{10}^{-6} is used in many similar geometry problems.

### PROBLEM:

We have to find the minimum time taken by Chef to cross N lanes without getting hit by a car (i.e. distance Dist between Carâs front or side and Chef must be such that Dist> {10}^{-6}). All relevant information like Carâs initial position, velocity, direction and length are provided to us.

### QUICK EXPLANATION:

The logic and math of this problem is very easy to get, and hence the problem boils down to careful and accurate implementation. We divide the solution into cases, like when Chef will have to wait for the car, when Chef can cross lane without waiting for car etc. We must make sure to use correct data-types, and mind the gap of {10}^{-6}.

### EXPLANATION:

There isnât much to explore in this question with respect to time complexity, as a straight-forward O(N) solution is possible. We will discuss the various approaches used by Editorialist and Tester. Setterâs approach is a hybrid between the two, and hence will be left as an exercise to work on (his code is commented for easier understanding ).

**1. Editorialistâs Solution-**

My basic idea is inspired from divide and conquer. (Divide the problem into cases which are easy to conquer xD).

The car passes Chef when the back of car is at y=0. So I calculated a few things, such as back of car when t=0 (i.e. B_0) and back of car when current moment (i.e B_t). I then identified the following cases-

**a.**If the car is moving in positive direction, and its back is ahead of y=0 at t=0 (i.e. car has crossed y=0 already), and vice-versa if car is moving in negative direction, OR if the car has already crossed the lane by the time Chef reaches lane i, then make Chef cross the lane immediately.

**b.** As an extension to first case, if the car cannot reach Chef by the time he crosses the lane, defined by front and rear of car being at a distance of at least {10}^{-6} by the time Chef crosses the lane, then make Chef cross the lane immediately.

**c.** For ALL other cases, car will hit Chef if he doesnât wait. Hence, add to ans the time taken by car to cross y=0 and by Chef to cross the lane.

Print upto 3 decimal places and we are done

**Testerâs approach-**

Mishaâs solution follows a similar method, but different conditions. The cases he identified were-

**a.** First check the direction.

**b.** For the respective direction, calculate the where the carâs rear will be when-

**i)** When Chef arrives at that lane.

**ii)**When Chef finishes crossing the lane, had he started immediately.

**c.** If, we observe that the car was at different side of y=0 at **i)** than it is at **ii)** (by checking location of carâs rear at **i)** and carâs front at **ii)**), it means it will hit Chef if Chef starts to cross immediately. Add time for car to cross to the answer.

**d.** Add time for Chef to cross the lane.

Refer to testerâs code for greater clarity.

Time Complexity- O(T*N) for both the approaches.

### SOLUTION:

### CHEF VIJJUâS CORNER:

**1.** This was a testing implementation problem. While the frustration a coder feels when he gets WA is understandable, it reaches to a whole new level when he knows that the logic is easy but its difficult to implement. But we cannot discard the fact that it is a necessary skill. Teaching importance of implementation, especially in a field which overlaps with concept of geometry, was one of our contest admin Mishaâs big aim. And I see many of you fared well :). To all those who didnt, I will say, better fail and get frustrated here, than fail at somewhere else where it might be more important for you to get that AC. Learn from this experience, as solving this question taught me a few things as well

**2.**I can recall a famous saying that-

''There is never too much Geometry!!''

- Somebody

So true a saying, lets complement it with a few Geometry, or related, problems

- Path by a Castle- Past ICPC question. Dont follow geeksforgeeks.com code for point inside a polygon part. That code is wrong.
- New Year and Curling- A decent Geometry problem.
- Car-pal Tunnel- In case anyone did not have enough of cars
- Broken Clock - A Trigonometry question, but I believe Trigonometry and Geometry go hand in hand.
- Point Inside a Polygon - Name is self descriptive