## 10378 - Complex Numbers

Moderator: Board moderators

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

### 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++;}
}

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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);" ....

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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:
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

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;

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),sort_func);
outdata();
printf("\n");
}
return 0;
}
[/cpp]

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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 Thank you much ! now it's working

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
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;
int count,x,sign,n;
double r,i,theta,*ans,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=='-')
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]=cos(y),ans[x]=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]*k);
if(ans[x]==0)
printf("+0.000i\n");
else
{
if(ans[x]>0)
printf("+%.3lfi\n",ans[x]*k);
else
printf("%.3lfi\n",ans[x]*k);
}
}
printf("\n");
}
}
int comp(const void* a,const void* b)
{
if(((double *)a)==((double *)b))
{
if(((double *)a)==((double *)b))
return 0;
else if(((double *)a)>((double *)b))
return -1;
else if(((double *)a)<((double *)b))
return 1;
}
else
{
if(((double *)a)=((double *)b))
return 0;
else if(((double *)a)>((double *)b))
return -1;
else if(((double *)a)<((double *)b))
return 1;
}
}
``````

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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)

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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:
Thanks Adrian for help 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)

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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)-(*(double **)b))>Epsilon)
{
if((*(double **)a)>(*(double **)b))
return -1;
else
return 1;
}
if(fabs((*(double **)a)-(*(double **)b))<Epsilon)
return 0;
if((*(double **)a)>(*(double **)b))
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])<=Epsilon)
printf("0.000");
else
printf("%.3lf",ans[x]*k);
if(fabs(ans[x])<=Epsilon)
printf("+0.000i\n");
else
{
if(ans[x]>0)
printf("+%.3lfi\n",ans[x]*k);
else if(ans[x]<0)
printf("%.3lfi\n",ans[x]*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

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <utility>
using namespace std;
pair<double, double> s;
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
``````
Thx in advance 