СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 6938

На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси Oy, а две оставшиеся — по разные стороны от оси Oy.

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

Описание входных данных.

В первой строке вводится одно целое положительное число — количество точек N. Каждая из следующих N строк содержит два целых числа: сначала координата x, затем координата y очередной точки.

Описание выходных данных.

Программа должна вывести одно число — максимальную площадь четырёхугольника, удовлетворяющего условиям задачи. Если такого четырёхугольника не существует, программа должна вывести ноль.

Пример входных данных:

6

0 0

2 0

0 2

3 −3

−5 −5

6 6

Пример выходных данных для приведённого выше примера входных данных:

11

Решение.

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