453 - Intersecting Circles

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » 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
Last edited by Adrian Kuegel on Thu Sep 02, 2004 5:47 am, edited 1 time in total.

User avatar
mathijs
New poster
Posts: 7
Joined: Tue Mar 04, 2003 5:15 pm
Location: Groningen, The Netherlands
Contact:

Post by mathijs » 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.

choyon_buet
New poster
Posts: 5
Joined: Mon Feb 24, 2003 5:28 pm
Location: BANGLADESH

can any one give some Input for 453

Post by choyon_buet » 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. :wink:

choyon_buet
New poster
Posts: 5
Joined: Mon Feb 24, 2003 5:28 pm
Location: BANGLADESH

Post by choyon_buet » 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. :roll:

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

453 WA

Post by b3yours3lf » 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]

samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

help me 453 why WA?????plzzzzz

Post by samueljj » 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]
novice programmer

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

Post by Maarten » Sat Oct 11, 2003 7:41 pm

two rules:

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

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

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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...
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

Post by Observer » 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 :lol: :lol:

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! :wink:)

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

453 WA, Please help

Post by fpmc » 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
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

Post by Observer » Sat Jun 12, 2004 6:00 pm

Please refer to the following link:

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

Post by fpmc » 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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » 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!

wolf
New poster
Posts: 34
Joined: Sun Aug 22, 2004 4:20 am
Location: Poland

My code

Post by wolf » 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 :D)

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]

Post Reply

Return to “Volume 4 (400-499)”