Задача "Треугольник" Нахождения минимального периметра.

@iCaesar · Регистрация: 25.10.2011

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

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

Все это должно браться из файла, такого вида:
Input
5 - Кол-во точек
0 0 -т1
1.3 0 -т2
-2 0.1 -т3
1 0 -т4
10 10 - т5

В выходной файл выведите три числа – номера точек, которые должны быть вершинами треугольника, чтобы его периметр был минимален. Если решений несколько выведите любое из них.
Запись ответа в файл, такого вида:
Output
1 2 4

Есть примерный код:

Pascal
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
type Tpoint = record { тип Точка }
    x: double; { координата x }
    y: double; { координата y }
  end;
 
const N = 6;
 
const PArr : array[1..N] of TPoint =
  ((x:1;y:1),
   (x:2;y:2),
   (x:4;y:6),
   (x:4;y:7),
   (x:6;y:2),
   (x:7;y:1)
   );
 
function Distance(t1, t2 : integer) : extended;
begin
  Distance := sqrt( sqr(PArr[t1].x-PArr[t2].x) + sqr(PArr[t1].y-PArr[t2].y)  )
end;
 
var i1, i2, i3, k : integer;
  ab, bc, ac, per, minPer : extended;
  i1m, i2m, i3m : integer;
begin
  k := 0;
  i1m := -1;
  minPer := 1e10;
  for i1:=1 to N do
    for i2:=i1+1 to N do
      for i3:=i2+1 to N do
       if (i1<>i2) and (i2<>i3) and (i1<>i3) then begin
          ab := Distance(i1, i2);
          bc := Distance(i2, i3);
          ac := Distance(i1, i3);
          per := (ab+bc+ac);
          Writeln(i1, ' ', i2, ' ', i3,
                ' ab=',ab:7:3, ' bc=',bc:7:3, ' ac=',ac:7:3,
                ' perimeter = ', per:7:3);
          if per<minPer then begin
             minPer := per;
             i1m := i1; i2m := i2;  i3m := i3;
          end;
          inc(k)
       end;
  WriteLn('Сочетаний всего: ',k);
  WriteLn('Минимальный периметер = ',minPer:7:3,
       ' в точках ',
          i1m, ' ', i2m, ' ', i3m);
  Readln
end.

Нужно переделать немного, чтобы точки брались из файла !!

@Konferans · 24.11.2011, 12:38

Объяви в var
f:file of integer;

А после begin
reset(f,x,y);

Только тебе нужна еще переменная, которая отвечает за количество строк (в примере 5)

@Puporev · 24.11.2011, 15:48

Файл в одном каталоге с программой.

Pascal
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
type Tpoint = record { тип Точка }
              x:real; { координата x }
              y:real; { координата y }
              end;
function Dist(t1, t2 : Tpoint):real;
begin
  Dist := sqrt( sqr(t1.x-t2.x) + sqr(t1.y-t2.y))
end;
 
var f:text;
    t:array[1..100] of TPoint;
    n,i,i1, i2, i3, k : integer;
    i1m, i2m, i3m : integer;
    minPer:real;
begin
assign(f,'input.txt');
reset(f);
read(f,n);
for i:=1 to n do
read(f,t[i].x,t[i].y);
close(f);
minPer := Dist(t[1],t[2])+Dist(t[2],t[3])+Dist(t[1],t[3]);
i1m:=1;
i2m:=2;
i3m:=3;
for i1:=1 to n-2 do
for i2:=i1+1 to n-1 do
for i3:=i2+1 to n do
if Dist(t[i1],t[i2])+Dist(t[i2],t[i3])+Dist(t[i1],t[i3])< minPer then
 begin
  minPer:=Dist(t[i1],t[i2])+Dist(t[i2],t[i3])+Dist(t[i1],t[i3]);
  i1m:=i1;
  i2m:=i2;
  i3m:=i3;
 end;
WriteLn('Минимальный периметер = ',minPer:0:2,' в точках ',
         i1m,'[',t[i1m].x:0:2,';',t[i1m].y:0:2,']','  ',
         i2m,'[',t[i2m].x:0:2,';',t[i2m].y:0:2,']','  ',
         i3m,'[',t[i3m].x:0:2,';',t[i3m].y:0:2,']');
end.

@iCaesar · 24.11.2011, 20:25 **[ТС]**

Спасибо огромное.

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@Konferans 31 / 31 / 9 Регистрация: 23.11.2011 Сообщений: 58
	24.11.2011, 12:38
	Объяви в var f:file of integer; А после begin reset(f,x,y); Только тебе нужна еще переменная, которая отвечает за количество строк (в примере 5) 0

@iCaesar 1 / 1 / 1 Регистрация: 25.10.2011 Сообщений: 42
	24.11.2011, 20:25 [ТС]
	Спасибо огромное. 0