453 - Intersecting Circles

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Last edited by Adrian Kuegel on Thu Sep 02, 2004 5:47 am, edited 1 time in total.

mathijs
New poster
Posts: 7
Joined: Tue Mar 04, 2003 5:15 pm
Location: Groningen, The Netherlands
Contact:
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
New poster
Posts: 5
Joined: Mon Feb 24, 2003 5:28 pm

can any one give some Input for 453

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
New poster
Posts: 5
Joined: Mon Feb 24, 2003 5:28 pm
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
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

453 WA

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
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

help me 453 why WA?????plzzzzz

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

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
two rules:

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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...
Last edited by little joey on Fri Jul 30, 2004 12:46 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Finally

I got Accepted after so long... yeah~

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

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
Last edited by fpmc on Thu Jun 17, 2004 8:26 am, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

http://online-judge.uva.es/board/viewtopic.php?t=563
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm
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
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
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
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

My code

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]