Beam in the Tunnel

Time limit1sMemory limit128 MB

Summary
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 n−1n-1 consecutive sections. The floor of each section is a straight, possibly sloped segment. The points [x1,y1],[x2,y2],…,[xn,yn][x_1, y_1], [x_2, y_2], \dots, [x_n, y_n], with x1<x2<⋯<xnx_1 < x_2 < \dots < x_n, are the vertices where the floor starts, ends, or where two sections meet. The ceiling runs exactly 11 meter above the floor, so the matching ceiling vertices are [xi,yi+1][x_i, y_i + 1].

Cross-section of the tunnel with the laser beam and light translators

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 x1,x2,…,xnx_1, x_2, \dots, x_n.

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 NN (2≤N≤10002 \le N \le 1000). Each of the next NN lines contains two numbers xix_i and yiy_i (−10000≤xi,yi≤10000-10000 \le x_i, y_i \le 10000), the coordinates of the ii-th floor vertex. The xix_i are given in strictly increasing order.

Output

Print a single integer — the minimal number of light translators required.

Examples4

  1. Example 1

    Input
    4
    1 1
    2 1
    3 2
    4 1
    
    Expected output
    1
    
  2. Example 2

    Input
    5
    1 1
    2 1
    3 2
    4 1
    5 2
    
    Expected output
    2
    
  3. Example 3

    Input
    2
    0 0
    5 0
    
    Expected output
    0
    
  4. Example 4

    Input
    5
    1 3
    2 3
    3 3
    4 3
    5 3
    
    Expected output
    0