10466 - How Far?

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10466 - How Far?

Post by Dominik Michniewski » Fri Apr 18, 2003 1:33 pm

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)

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

vector component

Post by shamim » Sat Apr 19, 2003 11:11 am

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. :wink:

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

Post by Dominik Michniewski » Wed Apr 23, 2003 8:16 am

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)

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

Looks ok

Post by shamim » Wed Apr 23, 2003 9:14 am

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

Post by Red Scorpion » Sat Apr 26, 2003 3:56 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.

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

wrong formula

Post by shamim » Sat Apr 26, 2003 8:54 am

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.

8)

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). :wink:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Sat Apr 26, 2003 9:46 am

Oh, how stupid Am I.

I have fixed my mistakes and got AC.
Thanks, shamim.
:lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol:

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

10466 - How Far?

Post by playerX » Tue Jun 15, 2004 3:06 pm

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
Location: Dhaka , Bangladesh
Contact:

10466 - WA?

Post by arif_pasha » Tue Aug 24, 2004 6:27 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Mon Aug 30, 2004 6:56 pm

Try the following input :wink:

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
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Thu Sep 09, 2004 10:53 pm

thanks solaris. At last accepted :lol: :lol:

rubendv
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm

10466 - Critical Inputs please!!!

Post by rubendv » Sun Mar 06, 2005 5:46 pm

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?

Thanks in advance!

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

Post by shamim » Mon Mar 07, 2005 12:43 pm

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

Post by rubendv » Mon Mar 07, 2005 8:10 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[0].x = 0.0;
res[0].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;
}

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

10466 WA - is my algo wrong?

Post by smilitude » Tue Apr 11, 2006 5:28 am

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 radius;
        double time;
    }body[52];
        
    while(scanf("%d %lf",&n, &t)==2) {
        for(i=0;i<n;i++) 
            scanf("%lf %lf",&body[i].radius, &body[i].time);
        dist=body[0].radius;
        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;
            dist=sqrt(pow(dist,2.)+pow(body[i].radius,2.) - (2*dist*body[i].radius*cos(angle))); //cosine rule
            printf(" %.4lf",dist);
        }
        printf("\n");
    }
return 0;
}
            
            
can anyone tell me what is wrong?
fahim
#include <smile.h>

Post Reply

Return to “Volume 104 (10400-10499)”