Page 1 of 2
10378 - Complex Numbers
Posted: Fri Oct 25, 2002 6:40 pm
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++;}
}
Posted: Sat Oct 26, 2002 5:09 pm
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);" ....
Posted: Sun Oct 27, 2002 4:43 pm
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...
Posted: Sun Oct 27, 2002 5:17 pm
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));
}
10378
Posted: Mon Oct 28, 2002 10:17 am
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]
Posted: Mon Oct 28, 2002 11:45 am
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).
10378
Posted: Mon Oct 28, 2002 2:22 pm
by Grayver
Thank you much ! now it's working
Posted: Mon Aug 18, 2003 2:48 pm
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.
Posted: Sat Jun 05, 2004 5:39 am
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;
}
}
Posted: Sat Jun 05, 2004 1:40 pm
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
Posted: Sat Jun 05, 2004 1:52 pm
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;
Posted: Sat Jun 05, 2004 3:29 pm
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
Best regards
DM
Posted: Sun Jun 06, 2004 4:52 am
by 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...
its very bad. precision error
Posted: Fri Jun 11, 2004 5:51 pm
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;
}
Posted: Mon Feb 28, 2005 4:22 am
by Antonio Ocampo
Please help me. I got WA several times. I guess is a precision error.
Thx in advance
