Commit90ebfb1

authored

Update minimum-number-of-lines-to-cover-points.py

1 parent489a02c commit90ebfb1Copy full SHA for 90ebfb1

File tree

-1

lines changed

-1

lines changed

Lines changed: 6 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -14,7 +14,7 @@ def minimumLines(self, points):`
`14`	`14`	`defgcd(a,b):# Time: O(log(a + b))`
`15`	`15`	`whileb:`
`16`	`16`	`a,b=b,a%b`
`17`		`-returna`
	`17`	`+returnabs(a)`
`18`	`18`
`19`	`19`	`defpopcount(x):`
`20`	`20`	`result=0`
`@@ -35,6 +35,11 @@ def ceil_divide(a, b):`
`35`	`35`	`a,b,c= (y2-y1),-(x2-x1),x1(y2-y1)-y1(x2-x1)`
`36`	`36`	`g=gcd(gcd(a,b),c)`
`37`	`37`	`a,b,c=a//g,b//g,c//g`
	`38`	`+forxin (a,b,c):`
	`39`	`+ifx!=0:`
	`40`	`+ifx<0:`
	`41`	`+a,b,c=-a,-b,-c`
	`42`	`+break`
`38`	`43`	`lookup[(a,b,c)].add((x1,y1))`
`39`	`44`	`lookup[(a,b,c)].add((x2,y2))`
`40`	`45`	`lines= [lforl,pinlookup.iteritems()iflen(p)>2]# filter to improve complexity`

Comments

(0)