Page 2 of 6
Posted: Mon Mar 10, 2003 1:52 pm
It seems Stefan removed the testcases from his homepage. I have put his testcases on my homepage under
http://www.uni-ulm.de/~s_akuege/453.in
.../453.sol

Posted: Mon Mar 10, 2003 6:25 pm
Mmm... funny, the only thing that was different was the case
1.0 1.0 0.0
1.0 1.0 0.0

where my program said "THE CIRCLES ARE THE SAME" and yours said (1.000,1.000). But my changed program that replicates this still gets a WA.
A few tests (using assert) showed that my program sometimes wants to output -0.000 on the judge data, although on my computer (running Windows) everything is fine. (And a program that explicitly outputs 0.000 by using

Code: Select all

``````sprintf(str, "%.3f", ans);
if(!strcmp(str, "-0.000"))
printf("0.000");
else
printf("%s", str);
``````
gets a WA too...)

Adrian, what does your program use as a floating-point precision value? I use 1E-12.

### can any one give some Input for 453

Posted: Mon Mar 17, 2003 2:30 am
I tried so hard to solve this problem.but i am getting WA continuosly.so can any one give me some critical sample Input and Output for this problem (453 (!))?please send some critical inputs for 453. Posted: Mon Mar 17, 2003 2:46 am
THANKS Adrian kuegel. i got all those inputs and their solutions from your webpage.thanks a lot. I found few bugs in my code ,and trying to remove them. ### 453 WA

Posted: Sat Aug 30, 2003 4:38 am
It's just ordinary mathematic problem, but I always got WA..
Is this because precision error??

[c]#include<stdio.h>
#include<math.h>

struct garis
{
double koefx, koefy, konst;
}g;

struct gabungan
{
double koefx2, koefx, konst;
}gab;

main()
{
double xc1, yc1, r1, xc2, yc2, r2;
double A1, B1, C1, A2, B2, C2;
double x1, y1, x2, y2, D, akarD, temp;
int ctr;
#ifndef ONLINE_JUDGE
freopen("453.in","r",stdin);
freopen("453.out","w",stdout);
#endif
while(scanf("%lf %lf %lf",&xc1, &yc1, &r1)==3)
{
A1=-2*xc1;
B1=-2*yc1;
C1=(xc1*xc1)+(yc1*yc1)-(r1*r1);
scanf("%lf %lf %lf",&xc2, &yc2, &r2);
A2=-2*xc2;
B2=-2*yc2;
C2=(xc2*xc2)+(yc2*yc2)-(r2*r2);
g.koefx=A1-A2;
g.koefy=B1-B2;
g.konst=C1-C2;
if(g.koefx==0.0 && g.koefy==0.0 && g.konst==0.0)
{
printf("THE CIRCLES ARE THE SAME\n");
continue;
}
if((xc1-xc2)*(xc1-xc2)+(yc1-yc2)*(yc1-yc2) > (r1+r2)*(r1+r2))
{
printf("NO INTERSECTION\n");
continue;
}
if(g.koefx==0.0)
{
if(g.koefy==0.0)
{
printf("NO INTERSECTION\n");
continue;
}
y1=y2=-g.konst/g.koefy;
gab.koefx2=1;
gab.koefx=A1;
gab.konst=(y1*y1)+(B1*y1)+C1;
akarD=sqrt((gab.koefx*gab.koefx)-(4*gab.koefx2*gab.konst));
x1=(-gab.koefx-akarD)/(2*gab.koefx2);
x2=(-gab.koefx+akarD)/(2*gab.koefx2);
if(x1>x2)
{
temp=x1;
x1=x2;
x2=temp;
}
}
else if(g.koefy==0.0)
{
if(g.koefx==0.0)
{
printf("NO INTERSECTION\n");
continue;
}
x1=x2=-g.konst/g.koefx;
gab.koefx2=1;
gab.koefx=B1;
gab.konst=(x1*x1)+(A1*x1)+C1;
akarD=sqrt((gab.koefx*gab.koefx)-(4*gab.koefx2*gab.konst));
y1=(-gab.koefx-akarD)/(2*gab.koefx2);
y2=(-gab.koefx+akarD)/(2*gab.koefx2);
if(y1>y2)
{
temp=y1;
y1=y2;
y2=temp;
}
}
else
{
g.koefx/=g.koefy;
g.konst/=g.koefy;
g.koefy=1;
gab.koefx2=1+(g.koefx*g.koefx);
gab.koefx=(2*g.koefx*g.konst)+A1+(B1*-g.koefx);
gab.konst=(g.konst*g.konst)+(B1*-g.konst)+C1;
D=(gab.koefx*gab.koefx)-(4*gab.koefx2*gab.konst);
if(D<0)
{
printf("NO INTERSECTION\n");
continue;
}
akarD=sqrt(D);
x1=(-gab.koefx-akarD)/(2*gab.koefx2);
x2=(-gab.koefx+akarD)/(2*gab.koefx2);
y1=(-g.koefx*x1)-g.konst;
y2=(-g.koefx*x2)-g.konst;
if(x1>x2)
{
temp=x1;
x1=x2;
x2=temp;

temp=y1;
y1=y2;
y2=temp;
}
else if(x1==x2)
{
if(y1>y2)
{
temp=y1;
y1=y2;
y2=temp;
}
}
/* cek valid titik potong */
ctr=0;
if(abs((x1-xc1)*(x1-xc1)+(y1-yc1)*(y1-yc1)-(r1*r1)) < 0.001) ctr++;
if(abs((x2-xc1)*(x2-xc1)+(y2-yc1)*(y2-yc1)-(r1*r1)) < 0.001) ctr++;
if(abs((x1-xc2)*(x1-xc2)+(y1-yc2)*(y1-yc2)-(r2*r2)) < 0.001) ctr++;
if(abs((x2-xc2)*(x2-xc2)+(y2-yc2)*(y2-yc2)-(r2*r2)) < 0.001) ctr++;

if(ctr!=4)
{
printf("NO INTERSECTION\n");
continue;
}
}
if(x1==x2 && y1==y2) printf("(%.3lf,%.3lf)\n",x1,y1);
else printf("(%.3lf,%.3lf)(%.3lf,%.3lf)\n",x1, y1, x2, y2);
}
return 0;
}[/c]

### help me 453 why WA?????plzzzzz

Posted: Sat Oct 11, 2003 4:20 pm
#include<stdio.h>
#include<math.h>
void input();
void calc(int p);
double x1,y1,r1,x2,y2,r2,d;
void main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
input();
}

void calc(int p)
{

double g1,g2,f1,f2,c1,c2,a,b,c,A,B,C,D,X1,X2,Y1,Y2;

g1=-x1; f1=-y1; c1=g1*g1+f1*f1-r1*r1;
g2=-x2; f2=-y2; c2=g2*g2+f2*f2-r2*r2;

a=g1-g2;
b=f1-f2;
c=(c1-c2)/2.0;
/////////////////

if(b!=0)
{
A=1+(a*a)/(b*b);
B=(2.0*a*c/(b*b)) + 2*g1 - (2*a*f1/b);
C=(c*c)/(b*b)-(2*f1*c)/b +c1;

D=B*B-4*A*C;

X1= (-B+sqrt(D))/2*A;
X2= (-B-sqrt(D))/2*A;

Y1=-(a*X1+c)/b;
Y2=-(a*X2+c)/b;

}

if(b==0)
{

A=1+(b*b)/(a*a);
B=(2.0*b*c/(a*a)) + 2*f1 - (2*b*g1/a);
C=(c*c)/(a*a)-(2*g1*c)/a +c1;

D=B*B-4*A*C;

Y1= (-B+sqrt(D))/2*A;
Y2= (-B-sqrt(D))/2*A;

X1=-(b*Y1+c)/a;
X2=-(b*Y2+c)/a;

}

/////////////////

if(D==0)
{
printf("(%.3lf,%.3lf)\n",X1,Y1);
}
else
{

if(X1==X2)
{
if(Y1<Y2)
{
printf("(%.3lf,%.3lf)",X1,Y1);
printf("(%.3lf,%.3lf)\n",X2,Y2);
}
else
{
printf("(%.3lf,%.3lf)",X2,Y2);
printf("(%.3lf,%.3lf)\n",X1,Y1);
}
}
else
{
if(X1<X2)

{
printf("(%.3lf,%.3lf)",X1,Y1);
printf("(%.3lf,%.3lf)\n",X2,Y2);
}
else
{
printf("(%.3lf,%.3lf)",X2,Y2);
printf("(%.3lf,%.3lf)\n",X1,Y1);
}
}

}

p++;//emni;
}

void input()
{
while(scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&r1,&x2,&y2,&r2)==6)
{
d=sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
if(d==0)
{
if(r1==r2){printf("THE CIRCLES ARE THE SAME\n");continue; }
else {printf("NO INTERSECTION\n");continue;}
}
else
{
if(r1+r2<d){printf("NO INTERSECTION\n");continue;}
if(r1+r2==d){calc(1);continue;}
if(r1+r2>d)
{
if(r1-r2<d||r2-r1<d){calc(2);continue;}
if(r1-r2==d||r2-r1==d){calc(1);continue;}
if(r1-r2>d||r2-r1>d){printf("NO INTERSECTION\n");continue;}
}

}
}

}[cpp][/cpp]

Posted: Sat Oct 11, 2003 7:41 pm
two rules:

Posted: Sat Jan 03, 2004 1:33 pm
Me too... I get WA too...

My program gives the same output as 453.sol for the given big test case, yet... still, no luck......

Any one can help me?? Please.

P.S. I set epsilon = 1E-10.

Posted: Mon Feb 16, 2004 1:01 pm
I'll add my program to the long list of WA codes. So if someone can have a look....
Needless to say it works for Stefan&Adrian's test data.
I use gcc 3.3.2 under linux (Knoppix), so I can't imagine I suffer from the -0.000 problem without detecting it.

The funny thing is, the problem has a special corrector (yellow flag), but still emits so much WAs.

[c]
/* CODE REMOVED, FINALY ACCEPTED */
[/c]

Finaly AC after a complete rewrite. It's a bl00dy shame that getting AC is so much dependant on making the right choices in rounding and comparing real numbers...

### Finally

Posted: Wed May 05, 2004 12:26 pm
I got Accepted after so long... yeah~

Stefan&Adrian's test data are very helpful. Thanks a lot  Hint: you may use a really BIG epsilon; sth like 1E-6 will do. (I've tried 1E-4 and surprisingly it gives me Accepted too! )

Adding epsilon to every number to be output is also a good idea.

Posted: Sat Jun 12, 2004 5:17 am
Problem 453: Intersecting two circles

The code below takes care of every possibilities that I can imagine, but obviously I'm missing some... Can those who got this question right help me out please...??

Code: Select all

``Code cut out``
Frank

Posted: Sat Jun 12, 2004 6:00 pm

http://online-judge.uva.es/board/viewtopic.php?t=563

Posted: Thu Jun 17, 2004 8:28 am
Thank you, I just had a very small bug in the code. Fixed it and got AC now.

By the way, I tried searching for messages relating to 453 before, but not successful. For example, if I go "Search" --> type in "453", I get not message, not even THIS ONE!! But obviously the title of this post has the text 453. Does anyone know why???

Frank

Posted: Thu Jul 08, 2004 4:27 pm
Such a strange thing... I use 1E-5 as Epsilon and my program may output -0.000 and get PE. I get AC later by using 1E-4 as Epsilon and
-0.000 dissapeared!

### My code

Posted: Thu Sep 02, 2004 1:41 am
Hi all !
I'm also trying to solve this, but my code keeps WA. Can someone help me ? (before I'll get frustrated )

Here's the code:
[cpp]
#include <iostream>
#include <stdio.h>
#include <math.h>

const double epsilon=1E-4;

using namespace std;

double x11,x22,y11,y22,r11,r22,a,d,xx1,xx2,yy1,yy2,ix,iy,h,temp,check;

inline double kw(double l)
{
return l*l;
}

void proceed()
{
if ((x11==x22)&&(y11==y22)&&(r11==r22))
{
cout << "THE CIRCLES ARE THE SAME\n";
return;
}
d=sqrt(kw(x22-x11)+kw(y22-y11));
if (d>r11+r22)
{
cout << "NO INTERSECTION\n";
return;
}
if (d<abs(r22-r11))
{
cout << "NO INTERSECTION\n";
return;
}
a=(kw(r11)-kw(r22)+kw(d))/(2*d);
h=sqrt(kw(r11)-kw(a));
ix=x11+(a*(x22-x11))/d;
iy=y11+(a*(y22-y11))/d;
xx1=ix+(h*(y22-y11))/d;
xx2=ix-(h*(y22-y11))/d;
yy1=iy-(h*(x22-x11))/d;
yy2=iy+(h*(x22-x11))/d;
check=sqrt(kw(xx1-x11)+kw(yy1-y11));
if ((check+epsilon>r11)&&(check-epsilon<r11))
{
temp=yy1;
yy1=yy2;
yy2=temp;
}
if ((h<epsilon)&&(h>-epsilon))
{
printf("(%.3f,%.3f)\n",xx1+epsilon,yy1+epsilon);
} else
{
printf("(%.3f,%.3f)(%.3f,%.3f)\n",xx2+epsilon,yy2+epsilon,xx1+epsilon,yy1+epsilon);
}
}

int main()
{
for (;;)
{
cin >> x11 >> y11 >> r11 >> x22 >> y22 >> r22;
if (!cin) break;
proceed();
}
return 0;
}
[/cpp]