На плоскости дан набор точек с целочисленными координатами. Необходимо найти четырёхугольник наибольшей площади с вершинами в этих точках, две вершины которого лежат на оси 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
Пример правильной, но неэффективной программы на языке Паскаль.
varcoord: 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.