INCREDIBLE wrong answer
Послано
KAV 15 мар 2006 19:07
The task is not difficult, but whyever I can't solve it :( WA #18. I use long double, that's why I think it isn't inaccuracy.
I use such an algorithm:
1. if BAC > 90 or ABC > 90 - all answers are min( AC, AB )
2. else: to 1 point = 2 * S(ABC) / AB, to all = max( AB, AC )
I believe that it is right
#include <stdio.h>
#include <math.h>
int Ax, Ay, Bx, By, Cx, Cy;
long double dL1, dLAll, L; // distances
void GetDistances()
{
// lens of vectors
int AB_x = Bx - Ax, AB_y = By - Ay, BC_x = Cx - Bx, BC_y = Cy - By, AC_x = Cx - Ax, AC_y = Cy - Ay;
// sides of ABC triangle
long double
/*.......*/AB = sqrtl( (long double)( AB_x*AB_x + AB_y*AB_y ) ),
/*.......*/AC = sqrtl( (long double)( AC_x*AC_x + AC_y*AC_y ) ),
/*.......*/BC = sqrtl( (long double)( BC_x*BC_x + BC_y*BC_y ) );
// scalar multiplications to count angles
int s_AB_AC = AB_x*AC_x + AB_y*AC_y, s_BA_BC = -AB_x*BC_x + -AB_y*BC_y;
if( Ax==Bx && Ay==By ) // AB is a dot
dL1 = dLAll = AC;
else // AB is a normal segment
{
// if some angle is more than 90, dL1 = min( AC, BC )
// else h = 2*S/AB. S = 0.5 * AC x AB. a x b = | x1*y2 - x2*y1 |
if( s_AB_AC < 0 ) dL1 = AC - L; // BAC > 90
else if( s_BA_BC < 0 ) dL1 = BC - L; // ABC > 90
else dL1 = fabsl( (long double) ( AC_x*BC_y - AC_y*BC_x ) ) / AB - L;
dLAll = ( AC > BC ? AC : BC ) - L; // biggest distance
}
if( dL1 < 0. ) dL1 = 0.;
if( dLAll < 0. ) dLAll = 0.;
}
int main()
{
scanf( "%d%d%d%d%d%d%lg", &Ax, &Ay, &Bx, &By, &Cx, &Cy, &L );
GetDistances();
printf( "%.2f\n%.2f", dL1, dLAll );
return 0;
}
Any ideas?..