Find minimum number of lines that could pass all the given points atleast once.

Правка en1, от zarrym911, 2021-02-13 14:19:42

An airline company wishes to establish a flight service in a new country. The company wants to provide flight service in such a way that will cover all the cities in the country with a minimum number of flights. Given the coordinates of all the cities in the country, the company has to determine the minimum number of straight routes necessary to cover all the cities. Write an algorithm to help the company find the minimum number of straight routes necessary to cover all the cities.

Input

The first line of the input consists of: two space-separated integers: numCities, representing the number of cities in the country(N). The next N lines consist of two space-separated integers: coordX and coordY representing the X and Y coordinates of the cities, respectively.

Output

Print an integer representing the minimum number of straight routes necessary to cover all the cities.

Constraints

O <= numCitiess <= 10^4

-10^3 < coordX, coordy < 10^3

Example

INPUT:

8

1 4

2 3

2 1

3 2

4 1

5 0

4 3

5 4

OUTPUT:

2

Explanation:

The points (2,1)(3,2)((4,3)(5,4) fall on a straight line and the points (1,4)(2,3)(3,2)(4,1)(5,0) fall on another straight line.

Теги #hiringchallenge, #geometry, #challenge

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский zarrym911 2021-02-13 14:23:56 2 Tiny change: 'ints**\n\nO <= numCit' -> 'ints**\n\n0 <= numCit'
en2 Английский zarrym911 2021-02-13 14:23:09 14
en1 Английский zarrym911 2021-02-13 14:19:42 1341 Initial revision (published)