84 lines
2.6 KiB
Python
84 lines
2.6 KiB
Python
def define_epsilon():
|
|
eps = 1.0
|
|
while eps + 1 > 1:
|
|
eps /= 2
|
|
eps *= 2
|
|
return eps
|
|
|
|
|
|
def is_between(a, b, c):
|
|
epsilon = define_epsilon()
|
|
cross_product = (c[1] - a[1]) * (b[0] - a[0]) - (c[0] - a[0]) * (b[1] - a[1])
|
|
|
|
# compare versus epsilon for floating point values, or != 0 if using integers
|
|
if abs(cross_product) > epsilon:
|
|
return False
|
|
|
|
dot_product = (c[0] - a[0]) * (b[0] - a[0]) + (c[1] - a[1]) * (b[1] - a[1])
|
|
if dot_product < 0:
|
|
return False
|
|
|
|
squared_length_b_a = (b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1])
|
|
if dot_product > squared_length_b_a:
|
|
return False
|
|
|
|
return True
|
|
|
|
|
|
def checkio(cakes):
|
|
lines = []
|
|
count_cakes = len(cakes)
|
|
i = 0
|
|
while i <= count_cakes - 1:
|
|
first_cake = cakes[i]
|
|
j = 0
|
|
while j <= count_cakes - 1:
|
|
if j <= i:
|
|
j += 1
|
|
continue
|
|
second_cake = cakes[j]
|
|
k = 0
|
|
while k <= count_cakes - 1:
|
|
if k == i or k == j:
|
|
k += 1
|
|
continue
|
|
third_cake = cakes[k]
|
|
if is_between(first_cake, second_cake, third_cake):
|
|
line_to_add = [first_cake, second_cake, third_cake]
|
|
for line in lines:
|
|
count = 0
|
|
to_add = []
|
|
if first_cake in line:
|
|
count += 1
|
|
else:
|
|
to_add.append(first_cake)
|
|
if second_cake in line:
|
|
count += 1
|
|
else:
|
|
to_add.append(second_cake)
|
|
if third_cake in line:
|
|
count += 1
|
|
else:
|
|
to_add.append(third_cake)
|
|
if count >= 2:
|
|
line_to_add = None
|
|
for t in to_add:
|
|
line.append(t)
|
|
|
|
if line_to_add is not None:
|
|
lines.append(line_to_add)
|
|
k += 1
|
|
j += 1
|
|
i += 1
|
|
|
|
print(lines)
|
|
return len(lines)
|
|
|
|
|
|
# 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
|