10378 - Complex Numbers

[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]

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]

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]

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));
}

[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[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]

[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]

Thank you much ! now it's working

[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]

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]

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


[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]

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

[htl]

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

[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[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;
}

[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