ОАО ”Крабодельня“ выбрала на плоскости множество точек с целочисленными координатами и отправила запрос в офис Крабоедов на поиск максимально возможной площади невырожденного треугольника (т.е. имеющего ненулевую площадь), не имеющего общих точек с \(Oy\), но одна сторона которого принадлежит \(Ox\).
Помогите Крабоедам сохранить работу и напишите программу, эффективную по времени и используемой памяти для решения этой задачи. Если такого треугольника не существует, необходимо вывести ”NO“. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся \(N\) — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.
Пример входных данных:
8
\(-10\) 0
2 0
0 4
3 3
7 0
5 5
4 0
9 \(-9\)
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать ”NO“.
Пример выходных данных для приведённого выше примера входных данных:
22.5
Так как треугольник не должен иметь общих точек с \(Oy\), имеет смысл рассматривать только такие треугольники, все вершины которого одновременно лежат выше или ниже оси. Найдем треугольник с максимальной площадью в верхней полуплоскости, затем аналогично в нижней и сравним их.
Поскольку одна сторона треугольника будет принадлежать \(Ox\), проще всего вычислять площадь как полупроизведение основания (сторона, принадлежащая \(Ox\)) и высоты (расстояние от основания до точки, не принадлежащей \(Ox\)).
Таким образом задача сводится к нахождению точки, координата \(y\) которой равна нулю, а координата \(x\) минимальна; точки, координата \(y\) которой равна нулю, а координата \(x\) максимальна; точки, максимально удаленной от оси \(Ox\).
Приведем пример решения задачи на языке \(Pascal\):
\[\begin{array}{l} var \; n,i,x,y,maxPosX,minPosX,maxNegX,maxNegAbsY,maxPosAbsY,s: \; longint;\\ \\ function\;max(a,b:\;longint):\;longint;\\ \quad begin\\ \quad if \; a>b\;then\; max:=a \; else \; max:=b;\\ \quad end;\\ \\ function\;min(a,b:\;longint):\;longint;\\ \quad begin\\ \quad if \; a>b\;then\; min:=b \; else \; max:=a;\\ \quad end;\\ \\ begin\\ readln(n);\\ for\;i:=1\;to\;n\;do\\ \quad begin\\ \quad readln(x);\\ \quad readln(y);\\ \quad if\;x>0\;then\\ \quad\quad begin\\ \quad\quad if\;y=0\;then\\ \quad\quad\quad begin\\ \quad\quad\quad if\; minPosX=0 \; then\\ \quad\quad\quad\quad minPosX:=x;\\ \quad\quad\quad maxPosX:=max(maxPosX, x);\\ \quad\quad\quad minPosX:=min(minPosX, x);\\ \quad\quad\quad end\;else\\ \quad\quad\quad\quad maxPosAbsY:=max(maxPosAbsY, abs(y));\\ \quad\quad end;\\ \quad if\;x<0\;then\\ \quad\quad begin\\ \quad\quad if\;y=0\;then\\ \quad\quad\quad begin\\ \quad\quad\quad if\; maxNegX=0 \; then\\ \quad\quad\quad\quad maxNegX:=x;\\ \quad\quad\quad maxNegX:=max(maxNegX, x);\\ \quad\quad\quad minNegX:=min(minNegX, x);\\ \quad\quad\quad end\;else\\ \quad\quad\quad\quad maxNegAbsY:=max(maxNegAbsY, abs(y));\\ \quad\quad end;\\ \quad end;\\ s := max((maxPosX - minPosX) * maxPosAbsY, (maxNegX - minNegX) * maxNegAbsY);\\ writeln(s / 2 \; :1\; :1);\\ end.\\ \end{array}\]
Ответ: См. решение
