10734 - Triangle Partitioning

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

Moderator: Board moderators

Post Reply
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10734 - Triangle Partitioning

Post by .. »

The problem says that:

Code: Select all

A triangle can be divided into two equal triangle by drawing a median on its largest edge
Consider the sample
3 4 5
If I am correct, the 2 small triangles from the first division are (3, 2.5, 2.5) and (4, 2.5, 2.5)
So what is the actual meaning of "equal"??? :o
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Their area, but that's completely irrelevant for the problem.

Two triangles (a,b,c): a>=b, b>=c and (a',b',c'): a'>=b', b'>=c' are "similar" (i.e. have the same "style") iff a/a' == b/b' == c/c'.

If you split the two triangles (4,5/2,5/2) and (3,5/2,5/2) again, you get four equal triangles (5/2,2,3/2) (truely equal (congruent) this time), which are similar to the original triangle.
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Thanks, get AC :D
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.
Md. Aftabuddin
New poster
Posts: 3
Joined: Sun Jun 26, 2005 2:24 pm

10734

Post by Md. Aftabuddin »

[quote="little joey"]Their area, but that's completely irrelevant for the problem.

Two triangles (a,b,c): a>=b, b>=c and (a',b',c'): a'>=b', b'>=c' are "similar" (i.e. have the same "style") iff a/a' == b/b' == c/c'.

If you split the two triangles (4,5/2,5/2) and (3,5/2,5/2) again, you get four equal triangles (5/2,2,3/2) (truely equal (congruent) this time), which are similar to the original triangle.[/quote]

The area is equal in the case of isoceles,equilateral and right tringle but not for general tringle
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej »

How can I know when should I stop dividing the smaller triangles?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

If a triangle has congruity with a triangle which you already got, you could stop dividing it.

-----
Rio
Post Reply

Return to “Volume 107 (10700-10799)”