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
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def getReducedForm ( dy , dx ) : NEW_LINE INDENT g = gcd ( abs ( dy ) , abs ( dx ) ) NEW_LINE sign = ( dy < 0 ) ^ ( dx < 0 ) NEW_LINE if ( sign ) : NEW_LINE INDENT return ( - abs ( dy ) // g , abs ( dx ) // g ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( abs ( dy ) // g , abs ( dx ) // g ) NEW_LINE DEDENT DEDENT def minLinesToCoverPoints ( points , N , xO , yO ) : NEW_LINE INDENT st = dict ( ) NEW_LINE minLines = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT curX = points [ i ] [ 0 ] NEW_LINE curY = points [ i ] [ 1 ] NEW_LINE temp = getReducedForm ( curY - yO , curX - xO ) NEW_LINE if ( temp not in st ) : NEW_LINE INDENT st [ temp ] = 1 NEW_LINE minLines += 1 NEW_LINE DEDENT DEDENT return minLines NEW_LINE DEDENT xO = 1 NEW_LINE yO = 0 NEW_LINE points = [ [ - 1 , 3 ] , [ 4 , 3 ] , [ 2 , 1 ] , [ - 1 , - 2 ] , [ 3 , - 3 ] ] NEW_LINE N = len ( points ) NEW_LINE print ( minLinesToCoverPoints ( points , N , xO , yO ) ) NEW_LINE