<jupyter_start><jupyter_text>3.1. Мінімальний трикутникВ заданому довільному полігоні A0A1...An-1 знайти такі три вершини Ak, Ap та  Aq, щоб площа трикутника AkApAq була найменшою з можливих, а сам трикутник повністю знаходився всередині полігону.Технічні вимоги.Координати точок A0, A1, ..., An-1 - цілі числа.**Вхід.** Текстовий файл, у першому рядку n - кількість вершин полігону у наступних n рядках  - у кожному через пропуски координати вершин Ai (Aix ; Aiy), i=0, 1, ..., n-1.**Вихід.** Три номери вершин (нумерація вершин полігону - з нуля) і площа трикутника.![Мінімальний трикутник](img/triangle.png)<jupyter_code>from shapely.geometry import Polygon, Point<jupyter_output><empty_output><jupyter_text>Read file<jupyter_code>f = open("data/Test31_4.txt", "r")
f.read()
# n, *vertexes = list(filter(None, map(lambda x: list(map(lambda y: int(y), x.split())), f.read().splitlines())))
# n = n[0]
# if (n != len(vertexes)):
#     raise Exception("The number of vertexes is not {}".format(n))
# n, vertexes
figure = Polygon(vertexes)
figure
min_area = 999999
min_coordinates = []
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        for k in range(n):
            if i == k or j == k:
                continue
            triangle = Polygon([vertexes[i], vertexes[j], vertexes[k]])
            area = triangle.area
            if (area < min_area and area > 0 and figure.contains(triangle)):
                min_area = area
                min_coordinates = [i, j, k]
min_vertexes = list(map(lambda x: vertexes[x], min_coordinates))
min_area, min_coordinates, min_vertexes
Polygon(min_vertexes)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12605042016806722, 'fraction_numerical': 0.013205282112845138, 'mean_word_length': 3.5546448087431695, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '230098', 'license': 'MIT', 'n_tokens_mistral': 645, 'n_tokens_neox': 699, 'n_words': 165, 'path': 'task-3/Minimal inner triangle.ipynb', 'repo_name': 'kushkamisha/applied-programming', 'size': '1666'}