РЕШУ ЕГЭ — информатика

Задания

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

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

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

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

В первой строке вводится одно целое положительное число  — количество точек N.

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

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

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

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

0 −10

0 2

4 0

3 3

0 7

0 4

5 5

−9 9

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

Решение. Заметим, что раз искомый треугольник не должен иметь общих точек с осью ОХ, то все его вершины будут одновременно или ниже оси, или выше. Тогда найдём треугольник с максимальной площадью для верхней полуплоскости, для нижней, а потом выберем лучший из них.

Задачи для обеих полуплоскостей решаются аналогично, рассмотрим решение для положительной полуплоскости. Так как две точки будут лежать на оси ОУ, удобнее всего будет считать площадь треугольника по формуле S  =  a · h / 2, где a  — длина основания треугольника, лежащего на оси ОУ, а h  — длина перпендикуляра из третьей точки на ось ОУ.

Заметим, что если первые две точки лежат на оси ОУ, то третья точка на ней не лежит, иначе бы треугольник получился вырожденный. Значит, множество точек, подходящих на роль первых двух в этом треугольнике, и множество точек, подходящих на роль третьей точки, не имеют общих точек. Из этого следует, что можно независимо найти для треугольника максимальное основание и максимальную высоту и площадь получившегося треугольника будет максимальна.

Утверждается, что в таком случае в качестве трёх вершин нужно брать точку с нулевой абсциссой и максимальной ординатой, точку с нулевой абсциссой и минимальной ординатой и точку, максимально удалённую от оси ОУ. Не стоит забывать, что рассматривать необходимо только точки с положительной ординатой. Удобно было бы завести массив и три раза по нему пробежаться, но оптимальнее будет искать точки сразу при считывании.

Ниже приведён код решения на языке Pascal версии 2.6.2.

var n, i, x, y, maxPosY, minPosY, maxNegY, minNegY, maxNegAbsX, maxPosAbsX, s : longint;

function max(a, b : longint) : longint;

begin

if a > b then max := a else max := b;

end;

function min(a, b : longint) : longint;

begin

if a > b then min := b else min := a;

end;

begin

readln(n);

for i := 1 to n do

begin

read(x);

readln(y);

if y > 0 then

begin

if x = 0 then

begin

if minPosY = 0 then

minPosY := y;

maxPosY := max(maxPosY, y);

minPosY := min(minPosY, y);

end else

maxPosAbsX := max(maxPosAbsX, abs(x));

end;

if y < 0 then

begin

if x = 0 then

begin

if maxNegY = 0 then

maxNegY := y;

maxNegY := max(maxNegY, y);

minNegY := min(minNegY, y);

end else

maxNegAbsX := max(maxNegAbsX, abs(x));

end;

s := max((maxPosY - minPosY) * maxPosAbsX, (maxNegY - minNegY) * maxNegAbsX);

writeln(s / 2 :1:1);

end.

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Программа правильно работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку).	4
Программа работает верно, но размер используемой памяти зависит от длины используемой последовательности. Например, входные данные запоминаются в массиве или другой структуре данных (например, контейнер priority queue, set или map в C++), размер которого соответствует количеству прочитанных чисел. Допускается наличие от одной до трёх синтаксических ошибок. Возможно, в принципиально верно организованном вводе данных есть ошибка.	3
Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержатся ошибки при инициализации цикла анализа массива данных или обработке конца массива. Допускается наличие от одной до пяти синтаксических ошибок, описанных выше.	2
В программе есть блок выделения очередного участка возрастания, однако этот блок написан с ошибками. Допускается наличие от одной до пяти синтаксических ошибок, описанных выше	1
Прочее	0
Максимальный балл	4

Ключ