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

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

program c4;
var
    n: integer;
    x, y: integer;
    ymin, ymax: integer;
    ysearch: boolean;
    xmin, xmax: integer;
    i: integer;
    s: real;
begin
    ysearch := true;
    ymin:=0; ymax := 0;
    xmin := 0; xmax := 0;
    readln(n);
    for i:=1 to n do begin
        readln(x,y);
        if x=0 then begin
            if ysearch or (y < ymin) then ymin:=y;
            if ysearch or (y > ymax) then ymax:=y;
            ysearch:=false;
        end
        else if x < xmin then xmin:=x
        else if x > xmax then xmax:=x
    end;
    if (ymax>ymin) and (xmin < 0) and (xmax>0)
        then s := (xmax-xmin)*(ymax-ymin)/2
    else s := 0;
    writeln(s);
end.

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

DIM n AS INTEGER

DIM x, y AS INTEGER

DIM ymin, ymax AS INTEGER

DIM ysearch AS INTEGER

DIM xmin, xmax AS INTEGER

DIM i AS INTEGER

DIM s AS DOUBLE

ysearch = 1

ymin = 0: ymax = 0

xmin = 0: xmax = 0

INPUT n

FOR i = 1 TO n

INPUT x, y

IF x = 0 THEN

IF ysearch = 1 OR y < ymin THEN ymin = y

IF ysearch = 1 OR y > ymax THEN ymax = y

ysearch = 0

ELSEIF x < xmin THEN xmin = x

ELSEIF x > xmax THEN xmax = x

END IF

NEXT i

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

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

ELSE

s = 0

END IF

PRINT s

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

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