10964 - Strange Planet

[Antonio Ocampo]

Hi for all. I got WA in this problem . Could someone confirm this I/O or sharing with me another one?


Input

Code: Select all

1 1
3423 345223
564 1231
873 123
856 43
99 11
100000000 198437
87584 28323
9999913 762
1000000000 1000000000
0 0
9826 32
9567 823
-1 -1

Output

Code: Select all

0.00
339.91
5.83
9.85
13.34
7.00
5221.20
234.92
1809.24
0.00
0.00
47.71
38.90

Thx in advance

[intergalactic]

My AC program produces the following result

Code: Select all

0.00
339.91
5.83
9.85
13.34
7.00
5221.20
234.92
1810.20
0.00
0.00
47.71
38.90

[Antonio Ocampo]

Uhmmmmmmm I got a different output for

Code: Select all

9999913 762 

Now my question is WHY? I guess i'm using a right approach. Could anyone give me any critical I/O?

Regards

[Adrian Kuegel]

Did you try to debug the (x,y) positions you calculate for all small values? I guess that should help.

[Antonio Ocampo]

Thx for your reply Adrian. I've fixed a little mistake in my code However, I still get WA

Could you or someone else give me the outputs for these inputs?


Input

Code: Select all

123 1423
57 234
6723 546
733 785143
98743 12
2 43
16 852
7653 34
42 98
564 111
9999999 23
10000001 1000000000
1000 10000
871 2387
67676 2435
99999 99999
62 66565
0 1
1 0
-1 -1

Output

Code: Select all

17.80
12.08
68.07
518.19
181.73
4.24
14.14
44.65
10.20
17.49
1739.94
1737.59
72.01
38.21
129.71
0.00
139.86
1.00
1.00

Thx in advance

[Adrian Kuegel]

For:
10000001 1000000000
I get:
18467.79
(one point is at (1627, -609), the other at (-6281, 16080) ).

for all other values I get the same output.

[Observer]

Might the problem be integer overflow?

[Antonio Ocampo]

Thx a lot Adrian and Observer !!!!!!!!!! I've finally got AC It was an integer overflow error

Thx again and keep posting.

[Niaz]

I can't figure out the formula. Even I don't know, is there any stright forward formula exist or not. Plz give me some hints. Thanks in advance.

[sandy007smarty]

My code is working for all the above test cases provided above in the variuos posts. But still I m getting WA. I thought may be uva's compiler uses 2 bytes for int and then changed datatype to even long int and then to even long long. Still getting WA. plz help.

Code: Select all

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<long long,long long> pt;
pt findCartesian(long long a)
{
        if(a==0)
                return make_pair(0,0);
        long long n,x,y,b,dx=1,dy=-1;
        n=(long long)sqrt(1.0f*a/2);
        while(2*n*(n-1)<a)
                n++;
        b=2*n*(n-1);
        x=-1*(n-1);
        y=0;
        while(b!=a)
        {
                x=x+dx;
                y=y+dy;
                if(y==0)
                        dx=-1*dx;
                if(x==0)
                        dy=-1*dy;
                b--;
        }
        return make_pair(x,y);
}
int main()
{
        long long a,b;
        float ans;
        pt pt1,pt2;
        while(1)
        {
                scanf(" %lld%lld",&a,&b);
                if(a==-1&&b==-1)
                        break;
                pt1=findCartesian(a);
                pt2=findCartesian(b);
//              cout<<"("<<pt1.first<<","<<pt1.second<<") ("<<pt2.first<<","<<pt2.second<<")\n";
                ans = sqrt((pt1.first-pt2.first)*(pt1.first-pt2.first)+(pt1.second-pt2.second)*(pt1.second-pt2.second));
                printf("%.2f\n",ans);
        }
        return 0;
}

[sandy007smarty]

I got AC when i changed the variable ans from float to double. Still I don't understand how does that effect the answers as the precison required is only 2 digits after the decimal point. Any idea?

[Moha]

Of course it needs 2 digit, but float is not big enough to hold the result.
In acm you should always use double instead of float.

[sandy007smarty]

Thanx. I am already following it now.

[DD]

Just wondering that brute-force simulation can passed this or not although I use the algorithm almost used by everyone on this