Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 188750
29.01.2016, 23:23
0.00 руб.
0 3 1
Образование
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
На плоскости задано множество точек с целочисленными координатами.
Необходимо найти максимально возможную площадь невырожденного (т. е.
имеющего ненулевую площадь) треугольника, одна вершина которого
расположена в начале координат, а две другие лежат на биссектрисах углов,
образованных осями координат, и при этом принадлежат заданному
множеству. Если такого треугольника не существует, необходимо вывести
соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу
для решения этой задачи.
Программа считается эффективной по времени, если при увеличении
количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для
хранения всех необходимых данных не зависит от количества точек и не
превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите
язык программирования и его версию.

Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа – координаты
очередной точки.
Пример входных данных:
3
6 6
-8 8
9 7

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


Обсуждение

давно
Зенченко Константин Николаевич
Старший Модератор
31795
6196
01.02.2016, 11:33
общий
Цитата: Посетитель - 399097
Напишите эффективную по времени и по используемой памяти программу
для решения этой задачи.

Язык программирования какой?
Об авторе:
Мне безразлично, что Вы думаете о обо мне, но я рад за Вас - Вы начали думать.

давно
Лысков Игорь Витальевич
Посетитель
7438
7205
01.02.2016, 17:45
общий
Адресаты:
Судя по другим вопросам, исключительно - Паскаль
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Зенченко Константин Николаевич
Старший Модератор
31795
6196
05.02.2016, 11:47
общий
это ответ
Здравствуйте, Посетитель - 399097!

Смотрите приложение:
[code lang=pascal h=200]var
a,b,n,x,y:integer;
{функция поиска максимального абсолютного значения}
function max_abs(a,b:integer):integer;
begin
if a<abs(b)then max_abs:=abs(b)
else max_abs:=abs(a);
end;
begin
{вводим количество точек}
repeat
write('N:=');
readln(n);
until n>2;
{начальные значения}
a:=0;b:=0;
{цикл ввода}
repeat
{вводим точки по координатам}
write('x:=');readln(x);
write('y:=');readln(y);
{проверяем ввод}
if(abs(x)=abs(y))and(x<>0)then
begin
{определяем бисектрису и запоминаем значение}
if x*y>0 then a:=max_abs(a,x)
else b:=max_abs(b,x);
end;
dec(n);{следующая точка}
until n=0;
{проверяем наличие треугольника и выводим сообщение}
if a*b>0 then writeln('S:=',a*b)
else writeln('wrong triangle');
readln;
end.[/code]
Удачи!
Об авторе:
Мне безразлично, что Вы думаете о обо мне, но я рад за Вас - Вы начали думать.

Форма ответа