Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

Network management

At the University of Debrecen, Faculty of Informatics the lecturers got a new computer laboratory. The PCs are already inside, however the network is not connected yet. Since our administrators are quite busy it is our job to wire everything up by using as few network cable as possible.
Cabling must be done by using a modified bus topology:
  • Every machine has an x and y coordinate which tells its exact place in the room. the (0,0) coordinate can be anywhere in the room, thus it can happen that some PCs has negative coordinates.
  • You need to create a main cable which is parallel to the X-axis and spans from left to right. Its starting point is the x coordinate of the leftmost PC and its endpoint is the x coordinate of the rightmost one.
  • From this main cable you need to split the subcables which are actually going to the machines. A subcable is always perpendicular to the main cable.
  • The main cable can pass through machines. In this case we consider that machine "wired" (done).
  • The sub cables cannot pass through machines, so if two PCs has the same x coordinate then the main cable is either "between" them or the main cable passes through one of the machines.

Input

  • The first line of the input is a N positive integer which gives you the number of machines in the room;
  • The next N number of lines contains an x and y integer separated by a single space which gives you the coordinates of a particular machine.

Output

The output is a single positive integer which gives you the minimum required amount of cables to wire everything up.

Restrictions

  • 0 < N < 100000;
  • The correct solution is at most 263;
  • -230 ≤ x,y ≤ 230

Example

Input:
  1. 3
  2. 0 0
  3. 1 1
  4. 2 2
download as text file Output:
  1. 4
download as text file Input:
  1. 3
  2. 1 2
  3. 0 0
  4. 2 2
download as text file Output:
  1. 4
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019