10725 - Triangular Square

[Dreamer#1]

Hi

Can someone please check if the following Input/Output of my solution are ok? I am getting WA
may be I'm missing something silly.

thanks in advance.


Input

[cpp]
6
1000 1000 999
1000 1000 1000
999 888 777
999 998 999
999 990 10
999 999 1
[/cpp]

Output

[cpp]
215236.257741
215390.309173
158492.939609
214805.846416
18.666231
0.998001
[/cpp]

[little joey]

Code: Select all

215267.110596
215390.309173
164962.169646
214836.668343
18.666231
0.998001

You're missing something

[schindlersp]

your input in my WA solution



215267.110596
215390.309173
164962.169646
214836.668343
95.541129
0.998001



but input

999 990 10 (valid ????)
999 999 1 (valid ????)

I need help!! how solved this problem?

thanxx

Schindler [quote][/quote]

[legend12]

I think this problem can solve by using "simple equation".
but I got WA.

I don't know why..

something mistake?

INPUT
5
3 5 3
1000 999 998
1000 5 999
34 684 653
500 500 500

OUTPUT
1.550759
214989.983489
23.742773
178.932623
53847.577293[/code][/cpp]

[little joey]

The third number should be 23.743109.

I agree, this is a geometry problem, not a programming problem. But that's OK. Math sharpens your mind.

[schindlersp]

legend12 find u your problem?

my out put is == your

999 1000 5
23.742773 (wrong why???????)

my input test

7
2 2 2
6 6 6
999 999 999
999 1000 5
10 6 8
7 7 8
5 4 3

output

0.861561
7.754051
214959.743945
23.742773
11.755102
11.477323
2.938776


Somebody can say which to me "simple equation" used and which is special cases ?


Schindler

[little joey]

999 1000 5
23.742773 (wrong why???????)

Because 23.743109 is bigger than 23.742773

You place the square on the side with length 1000, but if you place it on the side with length 999, it can be slightly bigger.
It's a little difficult to draw this triangle, but try to imagine what's special about it and what that means for the position of the square as compared to the more 'standard' cases.

[schindlersp]

I try to place in the sides that are been valid.

However for case 999 1000 5 my equation not calculates value 23,742773 in none of the sides

What it is missing? or made a mistake in my code ..

[cpp]


scanf("%ld%ld%ld",L,L+1,L+2);

s = (L[0] + L[1] + L[2]) / (double) 2.00;
a = sqrt(s * (s-L[0])*(s-L[1])*(s-L[2]));

dm = 0;

for (e = 0; e < 3; e++)
{
h = (a * 2.00) / (double) L[e];
d = (L[e] * h) / (double)(L[e] + h);

l1 = sqrt((L[(e+1)%3] * L[(e+1)%3]) - (h * h));
l2 = sqrt((L[(e+2)%3] * L[(e+2)%3]) - (h * h));

if ((l1 <= L[e]) && (l2 <= L[e]) && (d >= dm)) dm = d;
}
printf("%.6lf\n",(dm*dm));

[/cpp]

thanks

Schindler

[little joey]

I'm sorry, but I don't understand your code, especially the thought behind the calcullation of d and the first two conditions in the if statement. And when I compile and run it (after adding some lines), it produces weird output. Maybe you should publish the code that produced the numbers from your earlier post.

[schindlersp]

[cpp]

//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

//---------------------------------------------------------------------------


int main(int argc, char* argv[])
{
long L[3];
double s, a, h, d, dm, l1, l2;
register int i , casos;
register int e;

scanf("%d",&casos);

for (i = 0; i < casos; i++)
{
scanf("%ld%ld%ld",L,L+1,L+2);

s = (L[0] + L[1] + L[2]) / (double) 2.00;
a = sqrt(s * (s-L[0])*(s-L[1])*(s-L[2])); // area of triangle

dm = 0; // max side of square

for (e = 0; e < 3; e++)
{
// area = h * b / 2 => h = area * 2 / b
h = (a * 2.00) / (double) L[e]; // height of triangle L[e] is base

d = (L[e] * h) / (double)(L[e] + h); // d is side of square


l1 = sqrt((L[(e+1)%3] * L[(e+1)%3]) - (h * h));
l2 = sqrt((L[(e+2)%3] * L[(e+2)%3]) - (h * h));

if ((l1 <= L[e]) && (l2 <= L[e]) && (d >= dm)) dm = d;
}
printf("%.6lf\n",(dm*dm));
}

return 0;
}
//---------------------------------------------------------------------------


[/cpp]


Thanxxs

Schindler[/img]

[little joey]

That is an elegant method, but it only works if the triangle has three acute angles.

If the side on which the square rests (L[e]) has an obtuse angle, the value of d will be too big because the square will partially lie outside the triangle. You rightfully ignore d if l1>L[e] or l2>L[e].

But that's not the whole story. In the case of an obtuse triangle, an other (smaller) square can be found lying on the side that has the obtuse angle, and this square can not be ignored, because in some cases it will be the biggest square possible. You can find this square by scaling down d. Draw the picture and you'll probably see what I mean. If you need more help, PM me. Your new code will look like:
[cpp]...
l1 = sqrt((L[(e+1)%3] * L[(e+1)%3]) - (h * h));
l2 = sqrt((L[(e+2)%3] * L[(e+2)%3]) - (h * h));

if (l1 > L[e]) { /* scale down d using l2 */ }
else if (l2 > L[e]) { /* scale down d using l1 */ }

if (d >= dm) dm = d;
...[/cpp]

[schindlersp]

little joey thanK .. I got AC I had really not seen the detail.

[schindlersp]

My name is Luiz Fernando Schindler

in the site of the ACM I get AC in problem 10725 I looked at time 0:00:074 when I go to look my name in ranklist has only one Renato Ramalho with this time... I was to look in problem 10714 it was in my position. What it happened?

List of 1 solved problems:
100

?????????????????????????????????????? BUT I SOLVED MORE

[..]

Seems the judge has some error, some other people also meet this problem
http://online-judge.uva.es/board/viewtopic.php?t=6565

I have emailed the judge, hope they will fix this soon.

[w k]

Hi,

Is it an input like:

500 100 400

valid one?

Should I handle such inputs?

Wojciech