11186 - Circum Triangle

[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.

[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.

[sclo]

Take a look at problem 11168 Airport as you have to do something similar there, but that problem is slightly easier to do.

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