На плоскости заданы своими координатами n точек. Найти такую тройку из них, чтобы площадь образованного ими треугольника была наибольшей.
Формат входного файла: в первой строке содержится целое число n. Каждая из следующих n строк состоит из двух действительных чисел — координат соответствующих точек.
Пример исходного файла:
5
1.0 1.0
3.0 1.0
3.0 4.0
1.0 6.0
5.0 3.0
Для указанных входных данных площадь максимального треугольника составит 10 единиц, образован этот треугольник будет точками #1, #4, #5.
Program LargestTriangle;
const
_n = 100; {maximum amount of points}
var
n: integer; {actual amount of points}
x,y: array[1.._n] of real; {array of points}
f: text;
i,i1,i2,i3: integer;
square_cur, square_max: real; {squares}
b1,b2,b3: integer; {best points}
{----------------------------------------------------------}
function distance(v,w:integer):real;
begin
{v,w are indexes for x,y array; returns distance}
distance := sqrt(sqr(x[v]-x[w])+sqr(y[v]-y[w]));
end;
{----------------------------------------------------------}
function square(j,k,l:integer):real;
{i,k,l are indexes for x,y array; returns square}
var
a,b,c: real; {triangle sizes}
p: real; {half-perimeter}
begin
a := distance(j,k);
b := distance(k,l);
c := distance(l,j); {LJ is Lincoln's son (Prison Break)}
p := 0.5*(a+b+c);
square := sqrt (p*(p-a)*(p-b)*(p-c));
end;
{----------------------------------------------------------}
begin
{reading data}
assign (f,'input.txt');
reset (f);
readln (f,n);
for i := 1 to n do
readln (f,x[i],y[i]);
close(f);
{running brute force}
square_max := 0;
for i1 := 1 to n-2 do
for i2 := succ(i1) to n-1 do
for i3 := succ(i2) to n do
begin
square_cur := square(i1,i2,i3);
if (square_cur > square_max) then
begin
b1 := i1; b2 := i2; b3 := i3;
square_max := square_cur;
end;
end;
{outputting our best}
writeln ('Max square = ',square_max:0:4,' (with points #',
b1,'(',x[b1]:0:4,',',y[b1]:0:4,'), #',
b2,'(',x[b2]:0:4,',',y[b2]:0:4,'), #',
b3,'(',x[b3]:0:4,',',y[b3]:0:4,')');
end.
|
Комментарии
|
Реклама:
Разработано в студии "Webous" — о проекте — сайта карта —Реклама: