Жукоед живет в плоскости. Он выбрал на плоскости множество точек с целочисленными координатами и попросил найти Жукодава максимально возможную площадь треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при этом принадлежат заданному множеству.
Помогите Жукодаву и напишите программу, эффективную по времени и используемой памяти для решения этой задачи. Если такого треугольника не существует, необходимо вывести ”NO“. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.
Пример входных данных:
3
6 0
0 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать ”NO“.
Пример выходных данных для приведённого выше примера входных данных:
24
Эффективная программа
Поскольку по условию просят найти максимальную площадь треугольника, очевидно, что две вершины лежат на разных осях, а их коориднаты имеют вид \((x, 0)\) и \((0, y)\). Любой такой треугольник является прямоугольным, а, следовательно, его площадь легко можно вычислить по формуле \(|x| \cdot |y| \cdot \frac {1}{2}\). Тогда найдем координаты вида \((x, 0)\) и \((0, y)\) с максимальными \(x\) и \(y\).
Приведем пример решения на языке \(C++\):
\[\begin{array}{l} \#include \; <iostream>\\ using \; namespace \; std; \\ \\ int \; main \; ()\\ \{ \\ \quad int \; N;\\ \quad cin >> N;\\ \quad float \; x, y, x\_max=0, y\_max=0, ans=0; \\ \quad for \; (int \; i=0; \; i<N; \; i++) \; \{ \\ \quad\quad cin>>x>>y; \\ \quad\quad if \; (x==0 \; \&\& \; abs(y)>y\_max)\\ \quad\quad\quad y\_max=abs(y); \\ \quad\quad if \; (y==0 \; \&\& \; abs(x)>x\_max) \\ \quad\quad\quad x\_max=abs(x); \\ \quad \} \\ \quad ans=x\_max*y\_max/2; \\ \quad if (ans==0) \\ \quad \quad cout << ''NO''; \\ \quad else \\ \quad \quad cout << ans; \\ \quad return \; 0; \\ \} \\ \end{array}\]
Неэффективная программа
В данном случае программа будет считаться неэффиктивной, если при ее решении вы использовали двумерный массив размером \(N \times 2\), в который сначала записываете значения всех данных координат. Такая программа является неэффективной по памяти.
Ответ: См. решение