453 - Intersecting Circles

[Adrian Kuegel]

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

[mathijs]

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.

[choyon_buet]

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.

[choyon_buet]

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.

[b3yours3lf]

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]

[samueljj]

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

[Maarten]

two rules:

(1) please print formatted code
(2) please tell us what is the problem about

[Observer]

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.

[little joey]

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

[Observer]

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.

[fpmc]

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

[Observer]

Please refer to the following link:

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

[fpmc]

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

[htl]

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!

[wolf]

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]