10725 - Triangular Square

[w k]

Hi,

Could somebody post more I/O? I'm still getting WA.

Thanks

Wojciech

[w k]

OK!

I got it.

Wojciech

[pureza]

Code: Select all

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

int main()
{
        int T[3],i,t;
        double l1,l2,m,h,s,p,r;

        cin >> t;
        while ( t-- )
        {
                cin >> T[0] >> T[1] >> T[2];

                p = (T[0]+T[1]+T[2]) / 2.0;
                s = sqrt( p*(p-T[0])*(p-T[1])*(p-T[2]) );

                // r  - Maximum Triangle Edge
                r = 0;
                for ( i = 0 ; i < 3 ; i++ )
                {
                        h = 2.00*s / (double)T[i];
                        m = T[i]*h / (double)(T[i]+h);

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

                        // If it is Obtuse Triangle..
                        // Reduce R by l1, l2
                        if ( l1 > T[i] )
                                m = T[i]*h / (h+l1);
                        else if ( l2 > T[i] )
                                m = T[i]*h / (h+l2);

                        r = max(r,m);
                }
                printf("%.6lf\n",(r*r));
        }
}

[/code]

[Sedefcho]

Could someone please verify this I/O ?

INPUT

Code: Select all

6
500 500 500
881 855 30
868 866 3
999 998 2
990 993 7
992 991 2

OUTPUT

Code: Select all

53847.577293
210.276309
4.962898
2.986635
39.376414
2.986541

Thanks in advance!

[schindlersp]

My AC:

53847.577293
210.276309
4.962898
2.986635
39.376414
2.986541

[Cosmin.ro]

I solved the problem some time ago assuming that one edge of the square is on one edge of the triangle, but I can't prove this ... Does anyone have a proof?

[sclo]

First, observe that the largest square must have at least a corner on all 3 sides of the triangle, then using proper parametrization, we can show using calculus that the only local maxima are when at least a side of the square lies on triangle.