Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
ax+by=c ; gcd(a,b)=1 ; O(N^2) solution in Clear category for The Rows of Cakes by pokosasa
def checkio(cakes):
def gcd(a,b):
if b==0:
return a
return gcd(b,a%b)
lines={}
for i,(x1,y1) in enumerate(cakes[:-1]):
for (x2,y2) in cakes[i+1:]:
(a,b)=(y1-y2,x2-x1)
gcd_a_b=gcd(a,b)
(a,b)=(a//gcd_a_b,b//gcd_a_b)
c=a*x1+b*y1
if (a,b,c) in lines:
lines[(a,b,c)]+=1
else:
lines[(a,b,c)]=1
return sum(v>=3 for v in lines.values())
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([[3, 3], [5, 5], [8, 8], [2, 8], [8, 2]]) == 2
assert checkio(
[[2, 2], [2, 5], [2, 8], [5, 2], [7, 2], [8, 2],
[9, 2], [4, 5], [4, 8], [7, 5], [5, 8], [9, 8]]) == 6
Oct. 9, 2019
Comments:
