Minimum lines to cover all points | C ++ program to get minimum lines to cover all the 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } pair < int , int > getReducedForm ( int dy , int dx ) { int g = gcd ( abs ( dy ) , abs ( dx ) ) ; bool sign = ( dy < 0 ) ^ ( dx < 0 ) ; if ( sign ) return make_pair ( - abs ( dy ) / g , abs ( dx ) / g ) ; else return make_pair ( abs ( dy ) / g , abs ( dx ) / g ) ; } int minLinesToCoverPoints ( int points [ ] [ 2 ] , int N , int xO , int yO ) { set < pair < int , int > > st ; pair < int , int > temp ; int minLines = 0 ; for ( int i = 0 ; i < N ; i ++ ) { int curX = points [ i ] [ 0 ] ; int curY = points [ i ] [ 1 ] ; temp = getReducedForm ( curY - yO , curX - xO ) ; if ( st . find ( temp ) == st . end ( ) ) { st . insert ( temp ) ; minLines ++ ; } } return minLines ; } int main ( ) { int xO , yO ; xO = 1 ; yO = 0 ; int points [ ] [ 2 ] = { { -1 , 3 } , { 4 , 3 } , { 2 , 1 } , { -1 , -2 } , { 3 , -3 } } ; int N = sizeof ( points ) / sizeof ( points [ 0 ] ) ; cout << minLinesToCoverPoints ( points , N , xO , yO ) ; return 0 ; }