Commit8d8f0e6

authored

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

1 parent292c3a3 commit8d8f0e6Copy full SHA for 8d8f0e6

File tree

-8

lines changed

-8

lines changed

Lines changed: 6 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -32,14 +32,12 @@ def ceil_divide(a, b):`
`32`	`32`	`x2,y2=points[j]`
`33`	`33`	`# (x-x1)/(x2-x1) = (y-y1)/(y2-y1)`
`34`	`34`	`# => (y2-y1)x - (x2-x1)y = x1(y2-y1) - y1(x2-x1)`
`35`		`-a,b,c= (y2-y1),-(x2-x1),x1(y2-y1)-y1(x2-x1)`
`36`		`-g=gcd(gcd(a,b),c)`
`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`
	`35`	`+dx,dy=x2-x1,y2-y1`
	`36`	`+g=gcd(dx,dy)`
	`37`	`+a,b=dx//g,dy//g`
	`38`	`+ifa<0or (a==0andb<0):`
	`39`	`+a,b=-a,-b`
	`40`	`+c=bx1-ay1`
`43`	`41`	`lookup[(a,b,c)].add((x1,y1))`
`44`	`42`	`lookup[(a,b,c)].add((x2,y2))`
`45`	`43`	`lines= [lforl,pinlookup.iteritems()iflen(p)>2]# filter to improve complexity`

Comments

(0)