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


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

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

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

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

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

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

3

6 6

-8 8

9 7

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

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

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

Решение.

Биссектрисами углов, образованных осями координат, служат две прямые: и Очевидно, что вершины невырожденного треугольника должны лежать на разных биссектрисах, их координаты должны иметь вид (a, a) и (b, –b). Площадь такого треугольника равна |a| · |b|. Эта площадь будет минимальной при минимально возможных ненулевых значениях  |a| и |b|.

 

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

 

program P27;

  var

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

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

    amin, bmin: integer;

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

    i: integer;

begin

  readln(N);

  amin:=0; bmin:=0;

  for i:=1 to N do begin

    readln(x,y);

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

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

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

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

  end;

  s:=amin*bmin;

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

  else writeln(s)

end.

 

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

var

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

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

mins: integer; {минимальная площадь}

a, b: integer;

i, j: integer;

begin

readln(N);

mins := MaxInt;

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] = points[i, 2]) and (points[i, 1] <> 0) then a := abs(points[i, 1]);

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

if (a*b < mins) and (a * b <> 0) then mins := a*b;

end;

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

else writeln(mins);

end.


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