% Exercise 13, problem 2
%
% Speed-up of Part 2 relative to Part 1: ________________
%
% Expected computation time for n=1000:
% * t1: ________
% * t2: ________
% * t3: ________

% Largest triangle given n points on a unit circle
% Writing efficient code

% Part 1
for n=100:50:200
theta = rand(n,1)*2*pi; % Angle of n random pts on the unit circle
% Compute the area of the largest triangle that can be formed by
% 3 of the n points
A = 0; % max area so far
for i=1:n
for j=1:n
for k=1:n
% Triangle with vertices at points i,j,k
% Calculate Cartesian coordinates
ci = cos(theta(i));
si = sin(theta(i));
cj = cos(theta(j));
sj = sin(theta(j));
ck = cos(theta(k));
sk = sin(theta(k));
% Area using Heron's Formula where dij, dik, djk are side
% lengths of the triangle
dij = sqrt((ci-cj)^2 + (si-sj)^2); % distance btw pts i,j
dik = sqrt((ci-ck)^2 + (si-sk)^2); % distance btw pts i,k
djk = sqrt((cj-ck)^2 + (sj-sk)^2); % distance btw pts j,k
s = (dij+dik+djk)/2;
Aijk = sqrt((s-dij)*(s-dik)*(s-djk)*s);
A = max(A, Aijk);
end
end
end
end

% Part 2

% Part 3

% Part 4