O(n^3) is a brute force approach.
Here's the idea for O(n^2): For each pair of points, compute the sum of area of all triangles that contains that edge in O(1) time. Some precomputation is needed for that to work. Recall that we can define the area in terms of cross product of 2 vectors, and the identity (a x c)+(b x c) = ((a+b) x c)
The idea for O(n) method is similar.
11186  Circum Triangle
Moderator: Board moderators

 New poster
 Posts: 23
 Joined: Fri Sep 01, 2006 10:17 am
 Location: CSE, SUST
I can't understand what you want to do. Please, explain more, because i am trying to solve this problem but still failure. (LAST POST)
Edited:
Because I could not the manage the sign of the triangle so the output will different than expected. Finally I success.
Thnx everybody who posted.
Edited:
Because I could not the manage the sign of the triangle so the output will different than expected. Finally I success.
Thnx everybody who posted.
Last edited by Piklu_sust on Fri Apr 27, 2007 11:52 am, edited 1 time in total.

 New poster
 Posts: 28
 Joined: Mon Nov 04, 2002 8:03 pm
 Location: South Korea, Seoul
 Contact:
O(n^2) algorithm
we know that trianglearea is
 (x1*y2) + (x2*y3) + (x3*y1)  (x2*y1) + (x3*y2) + (x1*y3)  / 2
simply, area of all of trianlges is ( A_ij ) * ( x_i ) * ( y_j ) / 2
if you know that A_ij for ( 1 <= i , j <= n )
then, you can calculate the all of triangles with complexity O(n^2)
addtionally,
the A_ij divide into two sides  plus, minus
for example,
when n=5,
plusside is
( with parameter n, row, col )
so,
area += func(n,i,j) * x * y[j] for all i,j
is all of area of triangles
ps.
 to get the coefficients , you have to sort the angles
 two sides are very similar. you can get the coefficients with one function and different parametes. ( func(n, i, j) and func( n, j, i ) )
 (x1*y2) + (x2*y3) + (x3*y1)  (x2*y1) + (x3*y2) + (x1*y3)  / 2
simply, area of all of trianlges is ( A_ij ) * ( x_i ) * ( y_j ) / 2
if you know that A_ij for ( 1 <= i , j <= n )
then, you can calculate the all of triangles with complexity O(n^2)
addtionally,
the A_ij divide into two sides  plus, minus
for example,
when n=5,
plusside is
and minusside is0 3 2 1 0
0 0 3 2 1
1 0 0 3 2
2 1 0 0 3
3 2 1 0 0
as you see, we can get the A_ij with complexity O(1)0 0 1 2 3
3 0 0 1 2
2 3 0 0 1
1 2 3 0 0
0 1 2 3 0
( with parameter n, row, col )
so,
area += func(n,i,j) * x * y[j] for all i,j
is all of area of triangles
ps.
 to get the coefficients , you have to sort the angles
 two sides are very similar. you can get the coefficients with one function and different parametes. ( func(n, i, j) and func( n, j, i ) )