## 11186 - Circum Triangle

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.

Piklu_sust
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.
Last edited by Piklu_sust on Fri Apr 27, 2007 11:52 am, edited 1 time in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Take a look at problem 11168 Airport as you have to do something similar there, but that problem is slightly easier to do.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### O(n^2) algorithm

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)

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 ) )