ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1215. Exactness of Projectile Hit

Look here. It's my code!
Pz. find good tests for it!
//1215_SB
#include <iostream>
#include <cmath>
using namespace std;
#define eps 0.000001
struct Point{
// ....};
inline double triangle_S(Point& pa, Point& pb, Point& pc){
//calculates square of truiangle...
}
inline long double min_dist_to_line(Point& A, Point& B, Point& C)
{
    //here are a big and fat bug :)
    Point S;
    S.x = (B.x + A.x)/2.0;
    S.y = (B.y + A.y)/2.0;
    long double res = 0.0;
    long double a = C.dist(A);
    long double b = C.dist(B);
    long double d = A.dist(B);
    long double s = C.dist(S);

    if((s < a)&&(s < b))
    {
        res = sqrt(a*a - ((a*a - b*b + d*d)/(2.0*d))*((a*a - b*b + d*d)/(2.0*d)));
    }
    else
        res = (a > b) ? b : a;
    return res;

}
Point a[103];
int main()
{
    int n, i;
//getting the data
    double S_of_target = 0.0;
    for (int i = 1; i <= n; i++)
    {
        S_of_target += triangle_S(Dolly, a[i], a[i+1]);
    }
    double S_of_target_from_Center = 0.0;
    for (int i = 1; i <= n; i++)
    {
        S_of_target_from_Center += triangle_S(Center, a[i], a[i+1]);
    }
    if (fabs(S_of_target_from_Center - S_of_target) < eps)
    {
        printf("0.000\n");
        return 0;
    }

    long double min = 9999999999999999999999.9;
    for(i = 1; i <= n; i++)
    {
    //////////////////////////////////
        double d_t_l = min_dist_to_line(a[i], a[i+1], Center);
        if(min - d_t_l > eps)
        {
            min = d_t_l;
        }
        /////////////////////
    }
    printf("%.3lf\n", 2.0*min);

    return 0;
}

Edited by author 23.02.2007 15:37
try this test:

-1000000 -1000000 3
0 1000000
-1000000 1000000
1000000 999531

[3999999.890]

your program output: 4000000.000 (fell the difference :))

I think your bug in min_dist_to_line function in criterion of existing normal line to section [A, B] from point C on plane. You may change it on criterion of existing obtuse angle in triangle. And you will get AC. Good luck.
I think that there are no difference between:
yours:
 res = sqrt(a + b + d) / d * sqrt(-a + b + d) * sqrt(a - b + d) * sqrt(a + b - d);
                   res /= 2.0;
and my:
 res = sqrt(a * a - ((a * a - b * b + d * d) / (2.0 * d)) *
                                   ((a * a - b * b + d * d) / (2.0 * d)));
Because I got AC with my variant.
The only one problem was in this:
I wrote this condition
if((s < a) && (s < b))
you wrote:
        if ((s1 > 0) && (s2 > 0))
s1 and s2 means:
       s1 = ( a * a - b * b + d * d);
       s2 = (-a * a + b * b + d * d);
So I just missed that the triangle can be not able to be calculated with this function!
Thank you very much!
Olecksandr Voeca [Lviv NU] wrote 23 February 2007 04:37
try this test:

-1000000 -1000000 3
0 1000000
-1000000 1000000
1000000 999531

[3999999.890]

your program output: 4000000.000 (fell the difference :))

I think your bug in min_dist_to_line function in criterion of existing normal line to section [A, B] from point C on plane. You may change it on criterion of existing obtuse angle in triangle. And you will get AC. Good luck.
by the way, this test is't correct.. and my programm solve it..

i have wa16( can anybody help me?



Edited by author 21.09.2008 22:36

Edited by author 21.09.2008 22:38
i've solved it.
i think 16th test is like this:
1999 0 3
2000 0
-2000 1
0 2000