Вниманию любителей головоломок и прочего олимпиадного программирования предлагается следующая задача.
Есть 5 фигур:
Программа на Pyhon, которыми они были нарисованы:
#!/usr/bin/env python3
# vim: set ai et ts=4 sw=4:
from shapely.geometry.polygon import Polygon
from shapely.affinity import rotate, translate
import matplotlib.pyplot as plt
def draw_polygon(p, color):
xs, ys = p.boundary.xy
plt.fill(xs, ys, color)
p1 = Polygon([(0,0), (15,0), (15,15), (0,15)])
p2 = Polygon([(0,0), (29, 0), (29, 29)])
p3 = Polygon([(0,0), (21, 0), (0, 21)])
p4 = Polygon([(0,0), (20.5, 0), (31.1, 10.5), (20.5, 21), (0, 21)])
p5 = Polygon([(0,0), (10.6, 10.6), (21.2, 0), (41.5, 21), (0, 21)])
p1 = translate(p1, 45, 5)
p2 = translate(p2, 0, 25)
p3 = translate(p3, 30, 25)
p4 = translate(p4, 38, 40)
p5 = translate(p5, 2, 2)
polygons = [p1, p2, p3, p4, p5]
colors = ['red', 'orange', 'yellow', 'green', 'blue']
dpi = 80
fig = plt.figure(dpi = dpi, figsize = (512 / dpi, 512 / dpi) )
plt.axis([0, 70, 0, 70])
for p, c in zip(polygons, colors):
draw_polygon(p, c)
fig.savefig('initial-state.png')
Необходимо написать программу (на любом языке), которая решает следующие задачи:
1. Собирает квадрат, используя 4 из 5 представленных фигур
2. Собирает квадрат из 5-и фигур
В обоих случаях необходимо отобразить решение графически. Следует принять во внимание, что размеры фигур не идеально точные, так как измерялись линейкой по реальному пазлу.
Оставляйте в комментариях код своего решения, а также за какое время он справляется с задачей.
P.S. Задача сложнее чем может показаться на первый взгляд.
