sru_31's blog

By sru_31, history, 4 weeks ago, In English

The e-commerce company "ShopWithMe" has to do the fastest delivery to its distribution centres due to festive sales. They have the data of all the distribution centre locations in the county. The company has only limited trucks available for deliveries. Therefore, the company wishes — to select the minimum number of straight-line routes that will connect all the distribution locations. To finish the delivery efficiently, trucks will deliver the products to those distribution centres which will be along these straight-line routes only. One truck will cover all the centres along one straight-line route. Write an algorithm to calculate the minimum number of trucks needed by the company.

Input :

No of Distribution centre locations: 7

Location (x,y) of distribution centres:

       1 4

       2 1
       0 -2

       4 1

       4 3

      -2 3

       1 1 

Output : 3

Explanation: The points (2,1), (4,1) and (-1,1) fall on a straight line: the points (4,3),(-2,3) fall on another straight line; and the coordinates (1,4) , (0, -2) fall on a third straight line. Hence there are 3 straight-line routes possible so 3 delivery trucks will be needed __ PS : This test was already finished yesterday

  • Vote: I like it
  • -20
  • Vote: I do not like it

4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

This problem not solvable under those constraints

  • »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    constraints are n<=10^3

    -10^3<=location_x , location_y<=10^3

    can you brief upon the approach to solve the problem