## 10378 - Complex Numbers

Moderator: Board moderators

### 10378 - Complex Numbers

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++;}
}
ossama_a
New poster

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

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);" ....
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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...
Guru

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

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[i].re));
if (fix(cplx[i].im)>=0) printf("+");
printf("%0.3lfi\n",fix(cplx[i].im));
}
Yarin
Problemsetter

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

### 10378

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[i].real<=0)&&(roots[i].real>-0.0005)) roots[i].real=+0.0;
if ((roots[i].imag<=0)&&(roots[i].imag>-0.0005)) roots[i].imag=+0.0;
printf("%.3lf",roots[i].real);
if (roots[i].imag>=0) printf("+");
printf("%.3lfi\n",roots[i].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[i].real=new_a;
roots[i].imag=new_b;
}
qsort((void *)roots,in_n,sizeof(roots[0]),sort_func);
outdata();
printf("\n");
}
return 0;
}
[/cpp]
Grayver
New poster

Posts: 2
Joined: Mon Oct 28, 2002 10:10 am

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).
Guru

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

### 10378

Thank you much ! now it's working
Grayver
New poster

Posts: 2
Joined: Mon Oct 28, 2002 10:10 am

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.

little joey
Guru

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

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.14159265358979323846int 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;   }}`
htl
Experienced poster

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

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)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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;
Guru

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

It was my problem - comparing doubles - I must remeber this hint and use it in future problems :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)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

After debugging, I found that not only my comp but some wrong use of pointers
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...
htl
Experienced poster

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

### its very bad. precision error

#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[i]=(make_pair(sg*cos(new_arg), sg*sin(new_arg)));
if((s[i].first>=-1e-6) && (s[i].first<=1e-6))
s[i].first=0;
if((s[i].second>=-1e-6) && (s[i].second<=1e-6))
s[i].second=0;
}
pair<double,double> x;
qsort(s, n, sizeof(x), func);
for(int i=0; i<n; i++)
{
printf("%.3lf", s[i].first);
if(s[i].second>=-1e-6)
printf("+");
printf("%.3lfi\n", s[i].second);
}

}
return 0;
}

abishek
Experienced poster

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

Code: Select all
`Cut after AC :)`

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

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Next