Дан массив точек. Найти в этом массиве точек треугольники с наименьшей и наибольшей площадью

@bad_programmerr · Регистрация: 31.10.2022

Студворк — интернет-сервис помощи студентам

Дан массив точек. Найти в этом массиве точек треугольники с наименьшей и наибольшей площадью. Нужно использовать отдельные классы для точек и треугольников. Для треугольников реализовать методы сравнения операторами >, <, =, >=, <=, ==, != (имеется ввиду использовать функции __le__, __ge__, __lt__,__gt__,__ne__,__eq__) Массив приложен в виде файла input2.txt
У меня есть код Python, но он не содержит эти функции. Пытался вставить, но успешного исхода так и не вышло. Подскажите как это реализовать.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import json
 
class AreaTriangle:
   
   def MinimumArea(self, point):
      lenth = len(point)
      result = 0
      for i in range(lenth):
         for j in range(i+1, lenth):
            for z in range(i+2, lenth):
               (x1, y1), (x2, y2), (x3, y3) = point[i],point[j],point[z]
               result = min(result, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
      return result
 
   def MaksimumArea(self, point):
      lenth = len(point)
      result = 0
      for i in range(lenth):
         for j in range(i+1, lenth):
            for z in range(i+2, lenth):
               (x1, y1), (x2, y2), (x3, y3) = point[i],point[j],point[z]
               result = max(result, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
      return result
   
list1 = AreaTriangle()
f1 = open('input2.txt')
s = f1.readline()
f1.close()
s = s.replace(']','] ')
s = s.replace(', ',',')
s=s.split()
a =[]
for i in range(len(s)):
    items = json.loads(s[i])
    a.append(items)
   
print('минимальная',' ',list1.MinimumArea(a))
print('максимальная',' ',list1.MaksimumArea(a))

@Gdez · 12.12.2022, 14:58

bad_programmerr, Так?:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def dist_2(self, other):
        return (self.x - other.x) ** 2 + (self.y - other.y) ** 2
 
 
class Triangle:
 
    def __init__(self, A, B, C):
        self.A = Point(*A)
        self.B = Point(*B)
        self.C = Point(*C)
 
        self.ab = self.A.dist_2(self.B)
        self.ac = self.A.dist_2(self.C)
        self.bc = self.B.dist_2(self.C)
        
 
    def coor(self):
        return (self.A.x, self.A.y),\
               (self.B.x, self.B.y),\
               (self.C.x, self.C.y)
    
    def sides(self):
        return round(self.ab**.5, 2), \
               round(self.ac**.5, 2),\
               round(self.bc**.5, 2)
    
    def verify_triangle(self):
        a, b, c = self.ab, self.ac, self.bc
        return 2*max(a, b, c) < a + b + c
    
    def square_triangle(self):
        a, b, c = self.ab**.5, self.ac**.5, self.bc**.5
        p = (a + b + c)/2
        return (p * (p - a) * (p - b) * (p - c))**.5
    
    def __gt__(self, other):
        return self.square_triangle() > other.square_triangle()
 
    def __lt__(self, other):
        return self.square_triangle() < other.square_triangle()
    
 
 
with open('input.txt') as f:
    points = f.readlines()[0].split('][')
    points[0] = points[0][1:]
    points[-1] = points[-1][:-1]
    points = [tuple(map(int, p.split(', '))) for p in points]
    
n = len(points)
 
flag = False
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            
            if flag:
                tr = Triangle(points[i], points[j], points[k])
                if tr.verify_triangle():
                    if tr.__gt__(tr_max):
                        tr_max = tr 
                    elif tr.__lt__(tr_min):
                        tr_min = tr 
            else:
                tmp = Triangle(points[i], points[j], points[k])
                if tmp.verify_triangle():
                    tr_max = tr_min = tmp
                    flag = True
 
print(tr_max.coor())
print(tr_max.sides())
print(tr_max.square_triangle(), '\n')
print(tr_min.coor())
print(tr_min.sides())
print(tr_min.square_triangle())

@bad_programmerr · 12.12.2022, 15:13 **[ТС]**

Gdez, здравствуйте! Очень красивый у вас код получился, спасибо за ваш ответ. Но правильный ответ наименьшей площади 0, а у вас выводит ~ 2.5. Но мне это все равно очень поможет, спасибо!

@Gdez · 12.12.2022, 15:25

bad_programmerr,

Python
1
2
3
4
5
...
    def verify_triangle(self):
        a, b, c = self.ab, self.ac, self.bc
        return 2*max(a, b, c) <= a + b + c
...

Добавлено через 57 секунд
Меньше или равно... Но это не треугольник в классическом понимании

@u235 · 12.12.2022, 15:32

Gdez, если меньше или равно, тогда можно эту проверку вообще выбросить или возвращать сразу True..

Если, конечно, нет дублирующихся точек..

@Gdez · 12.12.2022, 15:36

u235, Согласен

Писалось для существующих треугольников из множества точек

@u235 · 12.12.2022, 15:38

Gdez, да, я понял, это чтобы исключить вырожденные треугольники. Но как видим, треугольники с нулевой площадью в этой задаче допустимы..

@Gdez · 12.12.2022, 15:46

Тогда так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def dist(self, other):
        return ((self.x - other.x) ** 2 + (self.y - other.y) ** 2)**.5
 
 
class Triangle:
 
    def __init__(self, A, B, C):
        self.A = Point(*A)
        self.B = Point(*B)
        self.C = Point(*C)
 
        self.ab = self.A.dist(self.B)
        self.ac = self.A.dist(self.C)
        self.bc = self.B.dist(self.C)
        
 
    def coor(self):
        return (self.A.x, self.A.y),\
               (self.B.x, self.B.y),\
               (self.C.x, self.C.y)
    
    def sides(self):
        return round(self.ab, 2), \
               round(self.ac, 2),\
               round(self.bc, 2)
    
    def square_triangle(self):
        a, b, c = self.ab, self.ac, self.bc
        p = (a + b + c)/2
        return (abs(p * (p - a) * (p - b) * (p - c)))**.5
    
    def __gt__(self, other):
        return self.square_triangle() > other.square_triangle()
 
    def __lt__(self, other):
        return self.square_triangle() < other.square_triangle()
    
 
 
with open('input.txt') as f:
    points = f.readlines()[0].split('][')
    points[0] = points[0][1:]
    points[-1] = points[-1][:-1]
    points = [tuple(map(int, p.split(', '))) for p in points]
    
n = len(points)
 
flag = False
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            
            if flag:
                tr = Triangle(points[i], points[j], points[k])
                if tr.__gt__(tr_max):
                    tr_max = tr 
                elif tr.__lt__(tr_min):
                    tr_min = tr 
            else:
                tmp = Triangle(points[i], points[j], points[k])
                tr_max = tr_min = tmp
                flag = True
 
print(tr_max.coor())
print(tr_max.sides())
print(tr_max.square_triangle(), '\n')
print(tr_min.coor())
print(tr_min.sides())
print(tr_min.square_triangle())

Добавлено через 1 минуту
abs() на 35-й строке из-за "ошибок" float

@Parramon · 12.12.2022, 16:00

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import json
 
class Triangle:
    def __init__(self, p1, p2, p3):
        self.a = p1
        self.b = p2
        self.c = p3
        self.area = 0.5 * abs(self.a[0] * (self.b[1] - self.c[1]) + self.b[0] * (self.c[1] - self.a[1]) + self.c[0] * (self.a[1] - self.b[1]))
 
    def __eq__(self, other):
        if isinstance(other, Triangle):
            return (self.area == other.area)
        return NotImplemented
 
    def __lt__(self, other):
        if isinstance(other, Triangle):
            return (self.area < other.area)
        return NotImplemented
 
    def __gt__(self, other):
        if isinstance(other, Triangle):
            return (self.area > other.area)
        return NotImplemented
 
    def __le__(self, other):
        if isinstance(other, Triangle):
            return (self.area <= other.area)
        return NotImplemented
 
    def __ge__(self, other):
        if isinstance(other, Triangle):
            return (self.area >= other.area)
        return NotImplemented
 
    def __ne__(self, other):
        if isinstance(other, Triangle):
            return (self.area != other.area)
        return NotImplemented
 
f1 = open('input2.txt')
s = f1.readline()
f1.close()
s = s.replace(']','] ')
s = s.replace(', ',',')
s=s.split()
a =[]
for i in range(len(s)):
    items = json.loads(s[i])
    a.append(items)
t = []
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        for k in range(j + 1, len(a)):
            t.append(Triangle(a[i], a[j], a[k]))
            if t[-1].area == 0:
                t.pop(-1)
min_t = min(t, key=lambda x: x.area)
max_t = max(t, key=lambda x: x.area)
print(f'Минимальная площадь у треугольника с координатами {min_t.a},{min_t.b},{min_t.c} равна {min_t.area}')
print(f'Максимальная площадь у треугольника с координатами {max_t.a},{max_t.b},{max_t.c} равна {max_t.area}')

Добавлено через 4 минуты
PS если 0 - это правильный ответ, то строки 55 и 56 удаляем

Новые блоги и статьи Все статьи Все блоги /
AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .

@bad_programmerr 0 / 0 / 0 Регистрация: 31.10.2022 Сообщений: 3
	12.12.2022, 15:13 [ТС]
	Gdez, здравствуйте! Очень красивый у вас код получился, спасибо за ваш ответ. Но правильный ответ наименьшей площади 0, а у вас выводит ~ 2.5. Но мне это все равно очень поможет, спасибо! 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	12.12.2022, 15:32
	Gdez, если меньше или равно, тогда можно эту проверку вообще выбросить или возвращать сразу True.. Если, конечно, нет дублирующихся точек.. 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	12.12.2022, 15:36
	u235, Согласен Писалось для существующих треугольников из множества точек 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	12.12.2022, 15:38
	Gdez, да, я понял, это чтобы исключить вырожденные треугольники. Но как видим, треугольники с нулевой площадью в этой задаче допустимы.. 1

Дан массив точек. Найти в этом массиве точек треугольники с наименьшей и наибольшей площадью

Решение

Решение