Page 2 of 2
Posted: Thu Mar 08, 2007 11:01 am
by sclo
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.
Posted: Sat Mar 10, 2007 9:54 am
by Piklu_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.
Posted: Sat Mar 10, 2007 6:58 pm
by sclo
Take a look at problem 11168 Airport as you have to do something similar there, but that problem is slightly easier to do.
O(n^2) algorithm
Posted: Wed Mar 28, 2007 10:02 pm
by Gaolious
we know that triangle-area 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,
plus-side is
0 3 2 1 0
0 0 3 2 1
1 0 0 3 2
2 1 0 0 3
3 2 1 0 0
and minus-side is
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
as you see, we can get the A_ij with complexity O(1)
( 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 ) )