На плоскости заданы своими координатами 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" — о проекте — сайта карта —Реклама: