Beam in the Tunnel
Time limit1sMemory limit128 MB
Given floor vertices of a unit-height tunnel, find the minimum number of translators so a straight beam segment between consecutive translators stays strictly inside.
- Level
Medium7 of 10
- Topics
- Geometry, Greedy, Binary search, Implementation
- Solved
- No attempts yet
Problem
A tunnel with a square (unit-height) cross-section is made of consecutive sections. The floor of each section is a straight, possibly sloped segment. The points , with , are the vertices where the floor starts, ends, or where two sections meet. The ceiling runs exactly meter above the floor, so the matching ceiling vertices are .

A laser beam enters the tunnel at its left end and must travel all the way to the right end, always staying strictly inside the tunnel (it may never touch the floor or the ceiling).
To steer the beam, light translators can be placed at section boundaries. A translator absorbs the incoming beam and re-emits it in any direction; the re-emitted beam may start from any point of that boundary, not only from the point where the incoming beam arrived. Because translators can be mounted only at section boundaries, a translator's horizontal position must be one of .
Between two consecutive translators (or between an end of the tunnel and a translator) the beam travels in a straight line and must stay strictly between the floor and the ceiling everywhere along that stretch.
Determine the minimal number of light translators required for the beam to pass through the entire tunnel.
Input
The first line contains an integer (). Each of the next lines contains two numbers and (), the coordinates of the -th floor vertex. The are given in strictly increasing order.
Output
Print a single integer — the minimal number of light translators required.