11186 - Circum Triangle

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post 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.
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
Location: Vancouver, BC, Canada
Contact:

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

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

O(n^2) algorithm

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

Post Reply

Return to “Volume 111 (11100-11199)”