Как найти максимальную площадь четырехугольника

Порядок следования сторон не влияет на площадь. Допустим, у нас имеется выпуклый четырёхугольник $%ABCD$% с основанием $%AD$%. Отрежем от него треугольник $%ABC$%, а потом приставим его к $%AC$% с разворотом. При этом порядок следования длин изменится — например, с $%3,4,5$% на $%4,3,5$%. Легко видеть, что при помощи таких действий можно получить любую из шести перестановок.

Максимум площади четырёхугольника с заданными длинами наблюдается у вписанного четырёхугольника. Эта задача встречается во многих сборниках. Сама максимальная площадь $%S$% может быть вычислена по формуле $$S^2=(p-a)(p-b)(p-c)(p-d),$$ где $%p$% — полупериметр. Для случая длин $%3,4,5,6$% имеем $%p=9$%, а площадь равна $%S=6sqrt{10}$%.

Сообщения без ответов | Активные темы | Избранное

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения

Решение.

Искомый четырёхугольник состоит из двух треугольников с общим основанием, лежащим на оси Ox, при этом один треугольник лежит выше этой оси, другой – ниже. Площадь четырёхугольника будет максимальной, если вершины на оси Ox будут расположены как можно дальше друг от друга, а вершины, не лежащие на этой оси,  — как можно дальше от неё. Программа читает исходные данные, не запоминая все точки в массиве. Для каждой точки проверяется её принадлежность оси Ox (условие y=0). Среди точек, лежащих на оси, необходимо найти наиболее далеко отстоящие друг от друга – они дадут наибольшее возможное общее основание двух треугольников. Это будут точки с наименьшим и наибольшим значением координаты x. Среди точек, не лежащих на оси Ox, надо найти две точки, расположенные по разные стороны от оси и как можно дальше от неё,  — они дадут наибольшие возможные значения высот треугольников. Это будут точки с наибольшим положительным и

наименьшим отрицательным значением координаты y.

Таким образом, задача сводится к нахождению максимального и минимального x среди точек, у которых y=0, максимального и минимального y среди остальных точек и нахождению площади четырёхугольника на основе этих данных.

Перед выводом результата необходимо убедиться в существовании искомого четырёхугольника.

Пример правильной и эффективной программы на языке Паскаль

program c4;

var

n: integer;

x, y: integer;

xmin, xmax: integer;

xsearch: boolean;

ymin, ymax: integer;

i: integer;

s: real;

begin

xsearch := true;

xmin := 0; xmax := 0;

ymin:=0; ymax := 0;

readln(n);

for i:=1 to n do begin

readln(x,y);

if y=0 then begin

if xsearch or (x < xmin) then xmin:=x;

if xsearch or (x > xmax) then xmax:=x;

xsearch:=false;

end

else if y < ymin then ymin:=y

else if y > ymax then ymax:=y

end;

if (xmax>xmin) and (ymin<0) and (ymax>0)

then s := (xmax-xmin)*(ymax-ymin)/2

else s := 0;

writeln(s);

end.

Пример правильной и эффективной программы на языке Бейсик

DIM n AS INTEGER

DIM x, y AS INTEGER

DIM xmin, xmax AS INTEGER

DIM xsearch AS INTEGER

DIM ymin, ymax AS INTEGER

DIM i AS INTEGER

DIM s AS DOUBLE

xsearch = 1

xmin = 0: xmax = 0

ymin = 0: ymax = 0

INPUT n

FOR i = 1 TO n

INPUT x, y

IF y = 0 THEN

IF xsearch = 1 OR x < xmin THEN xmin = x

IF xsearch = 1 OR x > xmax THEN xmax = x

xsearch = 0

ELSEIF y < ymin THEN ymin = y

ELSEIF y > ymax THEN ymax = y

END IF

NEXT i

IF xmax > xmin AND ymin < 0 AND ymax > 0 THEN

s = (xmax — xmin) * (ymax – ymin) / 2

ELSE

s = 0

END IF

PRINT s

Пример правильной и эффективной программы на Алгоритмическом языке

алг c4

нач

цел n

цел x,y

цел xmin=0, xmax=0

лог xsearch=да

цел ymin=0, ymax=0

цел i

вещ s

ввод n

нц для i от 1 до n

ввод x, y

если y=0

то

если xsearch или xесли xsearch или x>xmax то xmax:=x все

xsearch:=нет

иначе

если yесли y>ymax то ymax:=y все

все

кц

если xmax > xmin и ymin < 0 и ymax > 0

то s:=(xmax-xmin)*(ymax-ymin)/2

иначе s:=0

все

вывод s

кон

Пример решения задачи А на языке Паскаль.

var
  coord: array[1..10, 1..2] of integer; {исходные данные}
  x, y: integer; {координаты очередной точки}
  xminpos, xmaxpos, yminpos, ymaxpos: integer; {координаты точек четырёхугольника с наибольшей площадью}
  s: real; {площадь четырёхугольника}
  i, j: integer;
begin
  xminpos := MaxInt; xmaxpos := -(MaxInt-1);
  yminpos := MaxInt; ymaxpos := -(MaxInt-1);
  for i := 1 to 10 do begin
  read(x, y);
  coord[i, 1] := x; coord[i, 2] := y;
  end;
  for i := 1 to 10 do begin
    if (coord[i, 2] = 0) and (coord[i, 1] < xminpos) then xminpos := coord[i, 1];
    if (coord[i, 2] = 0) and (coord[i, 1] > xmaxpos) then xmaxpos := coord[i, 1];
    if (coord[i, 2] <> 0) and (coord[i, 2] < yminpos) then yminpos := coord[i, 2];
    if (coord[i, 2] <> 0) and (coord[i, 2] > ymaxpos) then ymaxpos := coord[i, 2];
  end;
  if (xminpos = xmaxpos) or (yminpos = ymaxpos) or (xminpos = MaxInt) then
      s := 0
  else s := (xmaxpos - xminpos)*(ymaxpos-yminpos)/2;
  writeln(s);
end.