Page 1 of 1
10964 - Strange Planet
Posted: Tue Nov 15, 2005 4:19 am
by 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
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
Posted: Tue Nov 15, 2005 4:50 am
by 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
Posted: Wed Nov 16, 2005 6:13 am
by Antonio Ocampo
Uhmmmmmmm I got a different output for
Now my question is WHY?
I guess i'm using a right approach. Could anyone give me any critical I/O?
Regards
Posted: Wed Nov 16, 2005 12:01 pm
by Adrian Kuegel
Did you try to debug the (x,y) positions you calculate for all small values? I guess that should help.
Posted: Wed Nov 16, 2005 5:15 pm
by 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
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
Posted: Wed Nov 16, 2005 7:55 pm
by 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.
Posted: Thu Nov 17, 2005 4:03 am
by Observer
Might the problem be integer overflow?
Posted: Thu Nov 17, 2005 9:58 pm
by Antonio Ocampo
Thx a lot Adrian and Observer !!!!!!!!!! I've finally got AC
It was an integer overflow error
Thx again and keep posting.
Posted: Thu Nov 24, 2005 6:44 pm
by 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.
Posted: Thu Apr 20, 2006 7:11 pm
by 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;
}
got AC but doubts
Posted: Sun Apr 23, 2006 9:29 am
by 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?
Posted: Tue Apr 25, 2006 6:19 pm
by 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.
Posted: Sun Apr 08, 2007 7:50 pm
by sandy007smarty
Thanx. I am already following it now.
Re: 10964 - Strange Planet
Posted: Sun Feb 24, 2013 11:04 pm
by DD
Just wondering that brute-force simulation can passed this or not although I use the algorithm almost used by everyone on this