Разбор C4 25 апреля

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

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

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

Описание входных данных

В первой строке вводится одно целое положительное число – количество точек N.

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

Описание выходных данных

Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.

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

8

-10 0

2 0

0 4

3 3

7 0

5 5

4 0

9 -9

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

22.5

Решение:

program c4;

uses crt;
var
a:array[1..8] of array [1..2] of integer;
i,j,x,y,N:integer;
s1,s:real;

BEGIN
s:=0;
readln(N);
for i:=1 to 8 do
for j:=1 to 2 do
a[i,j]:=0;

for i:=1 to N do
begin
readln(x,y);
if y=0 then
if x>0 then
if x>a[2,1] then
begin
a[2,1]:=x;
if a[1,1]=0 then a[1,1]:=x;
end     else
if x<a[1,1] then a[1,1]:=x else
else
if x<a[5,1] then
begin
a[5,1]:=x;
if a[6,1]=0 then a[6,1]:=x;
end     else
if x>a[6,1] then a[6,1]:=x
else     {Y<>0}
if (y>0)and(x>0)then
if y>a[3,2] then a[3,2]:=y else
else
if (y>0)and(x<0)then
if y>a[7,2] then a[7,2]:=y else
else
if (y<0)and(x>0)then
if y>a[4,2] then a[4,2]:=y else
else
if (y<0)and(x<0)then
if y>a[8,2] then a[8,2]:=y;
end;

s1:=abs((a[2,1]-a[1,1])*a[3,2]);
if s1>s then s:=s1;
s1:=abs((a[2,1]-a[1,1])*a[4,2]);
if s1>s then s:=s1;
s1:=abs((a[6,1]-a[5,1])*a[7,2]);
if s1>s then s:=s1;
s1:=abs((a[6,1]-a[5,1])*a[8,2]);
if s1>s then s:=s1;

writeln(s:5:1);
END.