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


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

На плоскости задано множество точек с целочисленными координатами.

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

этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.

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

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

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

В первой строке задаётся 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; {координаты очередной точки}

    xmin, ymin: integer;

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

    i: integer;

begin

  readln(N);

  xmin:=0; ymin:=0;

  for i:=1 to N do begin

    readln(x,y);

    if (x=0) and (y<>0) and

      ((ymin=0) or (abs(y) < ymin)) then ymin:=abs(y);

 

    if (y=0) and (x<>0) and

      ((xmin=0) or (abs(x) < xmin)) then xmin:=abs(x);

  end;

  s:=xmin*ymin/2;

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

  else writeln(s)

end.


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