Minimum lines to cover all points | Utility method to get gcd of a and b ; method returns reduced form of dy / dx as a pair ; get sign of result ; method returns minimum number of lines to cover all points where all lines goes through ( xO , yO ) ; set to store slope as a pair ; loop over all points once ; get x and y co - ordinate of current point ; if this slope is not there in set , increase ans by 1 and insert in set ; Driver code to test above methods
function gcd ( a , b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } function getReducedForm ( dy , dx ) { let g = gcd ( Math . abs ( dy ) , Math . abs ( dx ) ) ; let sign = ( dy < 0 ) ^ ( dx < 0 ) ; if ( sign ) { return [ Math . floor ( - Math . abs ( dy ) / g ) , Math . floor ( Math . abs ( dx ) / g ) ] ; } else return [ Math . floor ( Math . abs ( dy ) / g ) , Math . floor ( Math . abs ( dx ) / g ) ] ; } function minLinesToCoverPoints ( points , N , x0 , y0 ) { let st = new Set ( ) ; let temp ; let minLines = 0 ; for ( let i = 0 ; i < N ; i ++ ) { let curX = points [ i ] [ 0 ] ; let curY = points [ i ] [ 1 ] ; temp = getReducedForm ( curY - yO , curX - xO ) ; if ( ! st . has ( temp . join ( " " ) ) ) { st . add ( temp . join ( " " ) ) ; minLines ++ ; } } return minLines ; } let xO , yO ; xO = 1 ; yO = 0 ; let points = [ [ - 1 , 3 ] , [ 4 , 3 ] , [ 2 , 1 ] , [ - 1 , - 2 ] , [ 3 , - 3 ] ] ; let N = points . length ; document . write ( minLinesToCoverPoints ( points , N , xO , yO ) )