## 10466 - How Far?

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### 10466 - How Far?

Could anyone tell me some special inputs for this problem ?

I don't know , that my algorithm is correct, maybe (and probably that is) is wrong If someone want, he/she can send me Windows executable to my own test (reading from stdin and writing to stdout) I'll be greatful for help Best regards and Happy Easter )

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### vector component

I do not know the algorithm that you are using, but i can tell you that you must use vector component.

At first i was trying it with trigonometry(cosine rule), but later i realized that this is an erroneous approach. Later i considered vector component and got AC. Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Why trigonometry are errornous ?
I find point in which every planet is placed in given moment of time, using formula like this:

If body b is in point (x,y) and angle between (x,y) and OX is alpha, that body b[i+1] is placed:

Code: Select all

``````alfa[i+1] = alfa[i] + (T % b[i+1].period)*2*PI/b[i+1].period
x' = x + b[i].r*cos(alfa[i+1]);
y' = y + b[i].r*sin(alfa[i+1]);
``````
where T is given time, b[x].period is time, in which body[x] make one full movevment around of body b[x-1] ....

Is this wrong ?

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Looks ok

it seems that your method is similar to mine ,

but the following line looks suspicious:

alfa[i+1] = alfa + (T % b[i+1].period)*2*PI/b[i+1].period

The angle for each planet is unique, it is not dependent on previous angle.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hi, I always got WA.
Is my algo correct ?

Code: Select all

``cut.. ``
Can someone said my algo correct / wrong ?

Thanks.
Last edited by Red Scorpion on Sat Apr 26, 2003 9:54 am, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### wrong formula

To Red Scorpion:

consider the following line:

angle = ((T%t) * 360.00) / (double)t;
x += r * cos((angle*pi)/360.00);
y += r * sin((angle*pi)/360.00);

first of all it is unnecessary to consider the angle in degrees at first,
you could to directly multiply T%t by 2*pi to get the angle. and coming to that the conversion formula (angle*pi)/360.00 is wrong,

it should be (angle*pi)/180.00 since (pi rad)==(180 degree). Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Oh, how stupid Am I.

I have fixed my mistakes and got AC.
Thanks, shamim.         playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

### 10466 - How Far?

Could someone post some testcases? I'm gettin' WA
I'm doing point rotation and then pythagoras formula to calculate the distance.
be cool...

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:

### 10466 - WA?

Can anyone tell me why my code is getting wa? I calculated the theta and then applied pythagoras formula to calculate the distance. Thanks in advance.
[cpp]
#include <stdio.h>
#include <math.h>

#define min(a,b) a<=b?a:b

const double pi=acos(-1.0);
double T;

double dist(double d,double r,double t)
{
double theta = pi*2.0*T/t;
double temp;

theta = min( (2.0*pi-theta), theta );

temp = fabs(d*d+r*r+2.0*d*r*cos(theta));

d = sqrt(temp);

return d;
}

int main()
{
int i,n;
double t;
double r,d;

freopen("d:/coding/input/v104/10466.txt","r",stdin);

while(scanf("%d %lf",&n,&T)==2)
{

scanf("%lf %lf",&r,&t);

printf("%.4lf",r);

d = r;

for(i=0;i<n-1;i++)
{
scanf("%lf %lf",&r,&t);
d = dist(d,r,t);

printf(" %.4lf",d);
}
printf("\n");
}

return 0;
}
[/cpp]
Last edited by arif_pasha on Thu Jan 06, 2005 4:28 pm, edited 1 time in total.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
Try the following input 3 2
20 4
30 4
40 4
Where's the "Any" key?

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:
thanks solaris. At last accepted  rubendv
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm

### 10466 - Critical Inputs please!!!

Hi, my solution for this problem has got WA. I already tested it locally and it works fine.

Can anyone send me some critical inputs, and the results your program gave?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
It is better that you describe your method. There are many wrong methods that would pass the sample as well as some critical case.

rubendv
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm
I use the angles between the sun and each planet. Here is my solution:

#include <stdio.h>
#include <math.h>

#define MAXBODIES (50)

typedef struct{
float x;
float y;
} point;

typedef struct{
int r;
int t;
} planet;

planet table[MAXBODIES + 1];
point res[MAXBODIES + 1];

void solve(int n, int t){
float alpha = 0.0;
for (int i = 1; i <= n; i++){
float w = (float)(2 * acos(-1)) / table.t;
res.x = (float)cos(alpha + w * t) * (float)table.r + (float)res.x;
res.y = (float)sin(alpha + w * t) * (float)table.r + (float)res.y;
alpha = alpha + w * t;
}
for (int i = 1; i < n; i++)
printf("%.4f ",sqrt(res.x * res.x + res.y * res[i].y));
printf("%.4f\n",sqrt(res[n].x * res[n].x + res[n].y * res[n].y));
}

int main(void){
int n, t;
scanf("%d %d",&n, &t);
res.x = 0.0;
res.y = 0.0;
int ri, ti;
for (int i = 1; i <= n; i++){
scanf("%d %d",&ri, &ti);
table[i].r = ri;
table[i].t = ti;
}
solve(n,t);
return 0;
}

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### 10466 WA - is my algo wrong?

I tried to use cosine rule here...

Code: Select all

``````/*
* 10466 how far
* submission 0
* coded at 120 pm on march 21, 2006
*
*/

#include <stdio.h>
#include <math.h>
#define PI (2.*(acos(0.)))

int main() {
double dist;
int n,i,j;
double t;
struct {
double time;
}body;

while(scanf("%d %lf",&n, &t)==2) {
for(i=0;i<n;i++)
printf("%.4lf",dist);
for(i=1;i<n;i++) {
double ti;
double angle;
ti=fmod(t,body[i].time);
angle=(ti/body[i].time)*2.*PI;
if(angle>PI) angle=angle-PI;
else angle=PI-angle;