кроссворды, задачки, головоломки

Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи.

Petruchek.Info

Поиск наибольшего по площади треугольника

Добавлено: 06.03.08 в 09:25
Метки: информатика

На плоскости заданы своими координатами 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.

Комментарии
Google says:
Комментарий от новенького:
Новенький является
Новенький не робот
Знаки на картинке: латинские буквы, арабские цифры


Есть на сайте: Онлайн кроссворды Задачи Онлайн игры Блог
Все работы, опубликованные на сайте — авторские, если не указано иное. Перепечатка возможна только с письменного разрешения владельцев ресурса, с обязательной ссылкой на сайт petruchek.info. Пишите нам: . Сайт должен работать в IE, FF, Opera, Safari.

Реклама:

Разработано в студии "Webous"о проектесайта карта

Реклама: . Восточный курьер. Курьер. Военно промышленный курьер.