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


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

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

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

Входные данные

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

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

3

6 0

0 8

9 7

Выходные данные

Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».

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

24

Решение.

Очевидно, что вершины невырожденного треугольника должны лежать на разных осях, их координаты должны иметь вид (x, 0) и (0, y). Площадь такого треугольника равна |x| · |y| / 2. Эта площадь будет максимальной при максимальных значениях |x| и |y|.

Пример правильной программы на Паскале:

program P27;

  var

    N: integer; {количество точек}

    x,y: integer; {координаты очередной точки}

    xmax, ymax: integer;

    s: real; {площадь}

    i: integer;

begin

  readln(N);

  xmax:=0; ymax:=0;

  for i:=1 to N do begin

    readln(x,y);

    if (x=0) and (abs(y)>ymax) then ymax:=abs(y);

    if (y=0) and (abs(x)>xmax) then xmax:=abs(x);

  end;

  s:=xmax*ymax/2;

  if (s=0) then

    writeln('Треугольник не существует')

  else writeln(s)

end.

 

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

var

points: array[1..10000, 1..2] of integer; {исходные данные}

N: integer; {количество точек}

maxs: real; {максимальная площадь}

a, b: integer;

i, j: integer;

begin

readln(N);

maxs := 0;

a := 0; b := 0;

for i := 1 to N do read(points[i, 1], points[i, 2]);

for i := 1 to N do

for j := 1 to N do begin

if (points[i, 1] = 0) and (points[i, 2] <> 0) then a := abs(points[i, 2]);

if (points[j, 1] <> 0) and (points[j, 2] = 0) then b := abs(points[j, 1]);

if (a*b>maxs) and (a * b <> 0) then maxs := a*b/2;

end;

if maxs = 0 then writeln('Треугольник не существует')

else writeln(maxs);

end.


Аналоги к заданию № 9777: 9813 Все