10378 - Complex Numbers

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

Moderator: Board moderators

ossama_a
New poster
Posts: 1
Joined: Fri Oct 25, 2002 6:33 pm

10378 - Complex Numbers

Post by ossama_a »

Hi
I solved this problem and the judge didn't accept
Do anyone know something special about it?

this is my rejected solution :-?

//10378
#include<fstream>
#include<iostream>
#include<math.h>
#include<set>
using namespace std;

struct cnum
{
double a,b;
bool operator <(const cnum &n) const
{
return a>n.a || a==n.a && b>n.b;
}
};

//ifstream ifs("complex.in");
//ofstream ofs("complex.out");
istream &ifs=cin;
ostream &ofs=cout;
void main()
{
int num=1;
while(!ifs.eof())
{
int a,b,power;
double r,ai,bi;
char sign,i;
ifs>>a>>sign>>b>>i>>power;
if (!ifs) break;
if(sign=='-')b=-b;
r=pow(a*a+b*b,.5);
double th=atan2(b,a);
double pi=acos(0)*2;
if (th<0) th+=pi*2;
ofs<<"Case "<<num<<":\n";
multiset<cnum> s;
for(int j=0;j<power;j++)
{
ai=r*cos((th+j*2*pi)/power);
bi=r*(sin((th+j*2*pi)/power));
cnum nu;
nu.a=ai;nu.b=bi;
s.insert(nu);
}

multiset<cnum>::iterator it;
for(it=s.begin();it!=s.end();it++)
{
ofs.precision(3);
ofs.setf(ios::fixed);
double a,b;
a=(*it).a;b=(*it).b;
if (a<0 && a>-0.0005) a=0;
if (b<0 && b>-0.0005) b=0;
ofs<<a<<(b>=0?'+':'-')<<fabs(b)<<'i'<<'\n';
}

ofs<<endl;
num++;}
}

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

Post by Dominik Michniewski »

Could anyone post here any input/output cases ?

I use in my solution de Moivre formula, but got WA ....

Regards
Dominik

PS> ossama, i think, that you could change value for "r"
to "r = pow(r,1/power);" ....

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

I think there are rounding problems, because I got WA when I rounded manually, but I got accepted with the rounding of %.3f. From the thread of problem 474 (http://acm.uva.es/board/viewtopic.php?t=59 )
I know that pascal has another rounding as C, so it is unlikely to get Accepted for this problem with PASCAL. Please someone correct me if he solved this problem with PASCAL.
It seems that %.3f works in another way than floor(1000*num+0.5)/1000.0
In my opinion there should be a special corrector program for this problem, that allows a difference of 0.001.
By the way, use a small epsilon for sorting...

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

I used the following "fix" function:
double fix(double v)
{
if (v>0) return v;
if (v>-0.0005) return 0.0;
return v;
}
and printed the complex numbers like this:
for(i=0;i<n;i++) {
printf("%0.3lf",fix(cplx.re));
if (fix(cplx.im)>=0) printf("+");
printf("%0.3lfi\n",fix(cplx.im));
}

Grayver
New poster
Posts: 2
Joined: Mon Oct 28, 2002 10:10 am

10378

Post by Grayver »

I can't find any bugs... :(
Can anybody help me ?
[cpp]
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define M_PI 3.1415926535897932384626433832795

struct my_compl
{ double real,imag; };

double a,b,n;
my_compl roots[101];

double sqr(double arg)
{
return arg*arg;
}

int sort_func(const void *a, const void *b)
{
my_compl tmpa,tmpb;
tmpa=*(my_compl *)a;
tmpb=*(my_compl *)b;
double tmp;
if (tmpa.real==tmpb.real)
{ tmp=(tmpb.imag-tmpa.imag); } else
tmp=(tmpb.real-tmpa.real);
if (tmp==0) return tmp;
else if (tmp<0) return (-1);
else return 1;
}

void outdata()
{
int ansnum;
ansnum=n;
for (int i=0;i<ansnum;i++)
{
if ((roots.real<=0)&&(roots.real>-0.0005)) roots.real=+0.0;
if ((roots.imag<=0)&&(roots.imag>-0.0005)) roots.imag=+0.0;
printf("%.3lf",roots.real);
if (roots.imag>=0) printf("+");
printf("%.3lfi\n",roots.imag);
}
}

main()
{
#ifndef ONLINE_JUDGE
*stdin=*fopen("inp.txt","rt");
#endif
int curcase=0;
int in_a,in_b,in_n;
while (scanf("%d%di %d",&in_a,&in_b,&in_n)==3)
{
curcase++;
a=in_a; b=in_b; n=in_n;
double r,phi;
r=sqrt(sqr(a)+sqr(b));
if ((a==0)&&(b==0)) phi=M_PI/2; else phi=atan2(b,a);
double r_mod;
r_mod=pow(r,1/n);
printf("Case %d:\n",curcase);
double cur_phi,new_a,new_b;
for (int i=0;i<in_n;i++)
{
cur_phi=(phi+2*M_PI*i)/n;
new_a=r_mod*cos(cur_phi);
new_b=r_mod*sin(cur_phi);
roots.real=new_a;
roots[i].imag=new_b;
}
qsort((void *)roots,in_n,sizeof(roots[0]),sort_func);
outdata();
printf("\n");
}
return 0;
}
[/cpp]

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

you shouldn't compare floating point numbers like that:
tmpa.real==tmpb.real
it is better to use fabs(tmpa.real-tmpb.real)<1e-9 (or another small value).

Grayver
New poster
Posts: 2
Joined: Mon Oct 28, 2002 10:10 am

10378

Post by Grayver »

:) Thank you much ! now it's working

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

It's been nearly a year now, and there still are no Pascal solutions. If been trying different rounding algorithms for a couple of hours now, but without succes.

It's realy sad that there has been no rejudge of this problem with a (stupidly simple out-of-the-box) special judge program. Rounding is both compiler and machine dependent, which makes it virtually impossible to reproduce the exact same results in another language, with another compiler or on another machine.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

After testing I found that there's something wrong with my comp function. Some outputs are correct but some are not. Could someone help me with my prog?

Code: Select all

#include<stdio.h>
#include<math.h>
#define Pi 3.14159265358979323846
int comp(const void*,const void*);
void main(void)
{
 char s[10];
 int count,x,sign,n;
 double r,i,theta,*ans[100],k,y;
 for(x=0;x<100;x++)
   ans[x]=(double *)malloc(sizeof(double)*2);
 for(count=1;scanf("%s %d",s,&n)!=EOF;count++)
   {
    if(s[0]=='-')
      sign=-1,x=1;
    else
      sign=1,x=0;
    for(r=0;;x++)
      if(s[x]>='0' && s[x]<='9')
        r=r*10+s[x]-'0';
      else
        break;
    r*=sign;
    for(i=0;s[x]!='i';x++)
      if(s[x]>='0' && s[x]<='9')
        i=i*10+s[x]-'0';
      else if(s[x]=='+')
             sign=1;
      else
        sign=-1;
    i*=sign;
    if(r>0 && i>=0)
      theta=acos(r/sqrt(r*r+i*i));
    if(r<=0 && i>0)
      theta=acos(r/sqrt(r*r+i*i));
    if(r<0 && i<=0)
      theta=Pi-asin(i/sqrt(r*r+i*i));
    if(r>=0 && i<0)
      theta=2*Pi+asin(i/sqrt(r*r+i*i));
    for(x=0,y=theta/n,k=2*Pi/n;x<n;x++,y+=k)
      ans[x][0]=cos(y),ans[x][1]=sin(y);
    qsort(ans,n,sizeof(double *),comp);
    printf("Case %d:\n",count);
    for(x=0,k=pow(r*r+i*i,1.0/2/n);x<n;x++)
      {
       printf("%.3lf",ans[x][0]*k);
       if(ans[x][1]==0)
         printf("+0.000i\n");
       else
         {
          if(ans[x][1]>0)
            printf("+%.3lfi\n",ans[x][1]*k);
          else
            printf("%.3lfi\n",ans[x][1]*k);
         }
      }
    printf("\n");
   }
}
int comp(const void* a,const void* b)
{
 if(((double *)a)[0]==((double *)b)[0])
   {
    if(((double *)a)[1]==((double *)b)[1])
      return 0;
    else if(((double *)a)[1]>((double *)b)[1])
           return -1;
    else if(((double *)a)[1]<((double *)b)[1])
      return 1;
   }
 else
   {
    if(((double *)a)[1]=((double *)b)[1])
      return 0;
    else if(((double *)a)[1]>((double *)b)[1])
           return -1;
    else if(((double *)a)[1]<((double *)b)[1])
      return 1;
   }
}

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

Post by Dominik Michniewski »

Could anyone help me and tell , what I am doing wrong ??
I try many input cases and answers look to be OK. Maybe someone will found input where my program fails ? Or tell me why it's wrong ?

Best regards
DM

Code: Select all

ACCEPTED
Last edited by Dominik Michniewski on Sat Jun 05, 2004 3:28 pm, edited 1 time in total.
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)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

I can't give you a test case where it fails, but I hope I can tell you what is wrong :)
in your compare function you wrote
if(A->re < B->re) return 1;
if(A->re > B->re) return -1;
if(A->im < B->im) return 1;
if(A->im > B->im) return -1;
return 0;
But for comparing doubles, you always have to use epsilon.
Change it to:
if (fabs(a->re-B->re)>1e-6) {
if(A->re < B->re) return 1;
if(A->re > B->re) return -1;
}
if (fabs(a->im-B->im)<1e-6)
return 0;
if(A->im < B->im) return 1;
if(A->im > B->im) return -1;

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

Post by Dominik Michniewski »

Thanks Adrian for help :-)

It was my problem - comparing doubles - I must remeber this hint and use it in future problems :D:D:D

Best regards
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)

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

After debugging, I found that not only my comp but some wrong use of pointers :oops:
But after I recode the comp as below, I still got wa.

Code: Select all

 if(fabs((*(double **)a)[0]-(*(double **)b)[0])>Epsilon)
   {
    if((*(double **)a)[0]>(*(double **)b)[0])
      return -1;
    else
      return 1;
   }
 if(fabs((*(double **)a)[1]-(*(double **)b)[1])<Epsilon)
   return 0;
 if((*(double **)a)[1]>(*(double **)b)[1])
   return -1;
 else
   return 1;
and my output modified as below

Code: Select all

    for(x=0,k=pow(r*r+i*i,1.0/2/n);x<n;x++)
      {
       if(fabs(ans[x][0])<=Epsilon)
         printf("0.000");
       else
         printf("%.3lf",ans[x][0]*k);
       if(fabs(ans[x][1])<=Epsilon)
         printf("+0.000i\n");
       else
         {
          if(ans[x][1]>0)
            printf("+%.3lfi\n",ans[x][1]*k);
          else if(ans[x][1]<0)
                 printf("%.3lfi\n",ans[x][1]*k);
         }
      }
Maybe someone got AC can compare his/her code with mine and find out something wrong...

ps. Why do I compare a floating number with zero using Epsilon but not comparing a floating number with another? I feels puzzled...

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

its very bad. precision error

Post by abishek »

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <utility>
using namespace std;
pair<double, double> s[1000];
struct complex
{
double x, y;
complex(double a=0, double b=0) : x(a), y(b) { }
double abs() { return sqrt(x*x+y*y); }
double arg() { return atan2(y, x); }
};

int func(const void *a1, const void *b1)
{
const pair<double,double> *a=(const pair<double,double>*)a1;
const pair<double,double> *b=(const pair<double,double>*)b1;
if(fabs(a->first-b->first)>1e-6)
{
if(a->first>b->first)
return -1;
if(a->first<b->first)
return 1;
}
if(fabs(a->second-b->second)>1e-6)
{
if(a->second>b->second)
return -1;
if(a->second<b->second)
return 1;
}
return 0;
}

int main()
{
double a, b;
int n;
double pi=acos(0)*2;
int cano=0;
bool once=false;
while(scanf("%lf%lfi %d\n", &a, &b, &n)>0)
{
if(once)
printf("\n");
else
once=true;
complex c(a,b);
double mod=c.abs(), ar=c.arg();
double sg=pow(mod, 1.0/n);
printf("Case %d:\n", ++cano);
for(int i=0; i<n; i++)
{
double new_arg=(ar+2*i*pi);
new_arg/=n;
s=(make_pair(sg*cos(new_arg), sg*sin(new_arg)));
if((s.first>=-1e-6) && (s.first<=1e-6))
s.first=0;
if((s.second>=-1e-6) && (s.second<=1e-6))
s.second=0;
}
pair<double,double> x;
qsort(s, n, sizeof(x), func);
for(int i=0; i<n; i++)
{
printf("%.3lf", s.first);
if(s.second>=-1e-6)
printf("+");
printf("%.3lfi\n", s.second);
}

}
return 0;
}

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo »

Please help me. I got WA several times. I guess is a precision error.

Code: Select all


Cut after AC :)

Thx in advance :wink:
Last edited by Antonio Ocampo on Thu Mar 03, 2005 4:12 am, edited 1 time in total.

Post Reply

Return to “Volume 103 (10300-10399)”