Ис­ко­мый четырёхуголь­ник со­сто­ит из двух тре­уголь­ни­ков с общим ос­но­ва­ни­ем, ле­жа­щим на оси 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.