### Re: 453: Intersecting Circles

Posted:

**Sun Sep 15, 2013 4:39 am**One circle is inside the other.

The UVa Online Judge board

https://uva.onlinejudge.org/board/

Page **6** of **6**

Posted: **Sun Sep 15, 2013 4:39 am**

One circle is inside the other.

Posted: **Tue Jan 13, 2015 12:14 pm**

Getting WA. But why? My code passes all the input on this forum.

Here is my code:

Here is my code:

Code: Select all

```
#include <stdio.h>
#include <math.h>
#define eps 1e-4
int main()
{
double a, b, c, d, c1, c2, X1, X2, Y1, Y2, e, f, p, k, r, s;
while(scanf("%lf %lf %lf", &a, &b, &r)!=EOF)
{
scanf("%lf %lf %lf", &c, &d, &s);
e = c - a;
f = d - b;
p = sqrt(e*e + f*f);
k = (p*p + r*r - s*s)/(2.0*p);
if(fabs(a-c)<eps && fabs(b-d)<eps)
{
printf("(%.3lf,%.3lf)\n", a,b);
continue;
}
if(fabs(a-c)<eps && fabs(b-d)<eps && fabs(r-s)<eps)
{
printf("THE CIRCLES ARE THE SAME\n");
continue;
}
if(p>(r+s)+eps || (p+s)+eps<r || (p+r)+eps<s)
{
printf("NO INTERSECTION\n");
continue;
}
X1 = X2 = a + (e*k)/p;
Y1 = Y2 = b + (f*k)/p;
if(fabs(r*r - k*k)<1e-6);
else
{
X1 -= (f/p)*sqrt(r*r - k*k);
Y1 += (e/p)*sqrt(r*r - k*k);
X2 += (f/p)*sqrt(r*r - k*k);
Y2 -= (e/p)*sqrt(r*r - k*k);
}
if(X1<eps && X1>-eps)
X1=0.0;
if(X2<eps && X2>-eps)
X2=0.0;
if(Y1<eps && Y1>-eps)
Y1=0.0;
if(Y2<eps && Y2>-eps)
Y2=0.0;
if(X1+eps<X2)
{
printf("(%.3lf,%.3lf)", X1, Y1);
if(fabs(X1-X2)<eps && fabs(Y1-Y2)<eps);
else
printf("(%.3lf,%.3lf)", X2, Y2);
}
else
{
printf("(%.3lf,%.3lf)", X2, Y2);
if(fabs(X1-X2)<eps && fabs(Y1-Y2)<eps);
else
printf("(%.3lf,%.3lf)", X1, Y1);
}
printf("\n");
}
return 0;
}
```

Posted: **Tue Jan 13, 2015 10:59 pm**

I got AC by adding 5e-5 while printing the points, and 1e-6 for EPS everywhere else - including when determining if there are one or two intersection points.

Posted: **Wed Jan 14, 2015 11:45 am**

Sorry, I couldn't understand by your answer that where to use 1e-6 and where to use 5e-5. Please, say it clearly, with code.brianfry713 wrote:I got AC by adding 5e-5 while printing the points, and 1e-6 for EPS everywhere else - including when determining if there are one or two intersection points.

And how to determine when to use which value for EPS? Because it is so sensitive in programming contest.

Posted: **Thu Jan 15, 2015 1:28 am**

#define EPS1 1e-6

#define EPS2 5e-5

printf("(%.3lf,%.3lf)", X2 + EPS2, Y2 + EPS2);

Everywhere else use EPS1

On most problems a small EPS like 1e-8 works, but this problem is tricky

http://floating-point-gui.de/

#define EPS2 5e-5

printf("(%.3lf,%.3lf)", X2 + EPS2, Y2 + EPS2);

Everywhere else use EPS1

On most problems a small EPS like 1e-8 works, but this problem is tricky

http://floating-point-gui.de/

Posted: **Thu Jan 15, 2015 7:04 am**

Even getting WA!brianfry713 wrote:#define EPS1 1e-6

#define EPS2 5e-5

printf("(%.3lf,%.3lf)", X2 + EPS2, Y2 + EPS2);

Everywhere else use EPS1

On most problems a small EPS like 1e-8 works, but this problem is tricky

http://floating-point-gui.de/

Here is my changed code:

Code: Select all

```
#include <stdio.h>
#include <math.h>
#define eps 1e-6
#define EPS 5e-5
int main()
{
double a, b, c, d, c1, c2, X1, X2, Y1, Y2, e, f, p, k, r, s;
while(scanf("%lf %lf %lf", &a, &b, &r)!=EOF)
{
scanf("%lf %lf %lf", &c, &d, &s);
e = c - a;
f = d - b;
p = sqrt(e*e + f*f);
k = (p*p + r*r - s*s)/(2.0*p);
if(fabs(a-c)<eps && fabs(b-d)<eps)
{
printf("(%.3lf,%.3lf)\n", a+EPS,b+EPS);
continue;
}
if(fabs(a-c)<eps && fabs(b-d)<eps && fabs(r-s)<eps)
{
printf("THE CIRCLES ARE THE SAME\n");
continue;
}
if(p>(r+s)+eps || (p+s)+eps<r || (p+r)+eps<s)
{
printf("NO INTERSECTION\n");
continue;
}
X1 = X2 = a + (e*k)/p;
Y1 = Y2 = b + (f*k)/p;
if(fabs(r*r - k*k)<eps);
else
{
X1 -= (f/p)*sqrt(r*r - k*k);
Y1 += (e/p)*sqrt(r*r - k*k);
X2 += (f/p)*sqrt(r*r - k*k);
Y2 -= (e/p)*sqrt(r*r - k*k);
}
if(X1<eps && X1>-eps)
X1=0.0;
if(X2<eps && X2>-eps)
X2=0.0;
if(Y1<eps && Y1>-eps)
Y1=0.0;
if(Y2<eps && Y2>-eps)
Y2=0.0;
if(X1+eps<X2)
{
printf("(%.3lf,%.3lf)", X1+EPS, Y1+EPS);
if(fabs(X1-X2)<eps && fabs(Y1-Y2)<eps);
else
printf("(%.3lf,%.3lf)", X2+EPS, Y2+EPS);
}
else
{
printf("(%.3lf,%.3lf)", X2+EPS, Y2+EPS);
if(fabs(X1-X2)<eps && fabs(Y1-Y2)<eps);
else
printf("(%.3lf,%.3lf)", X1+EPS, Y1+EPS);
}
printf("\n");
}
return 0;
}
```

So, what to do?

Posted: **Fri Jan 16, 2015 2:07 am**

Input:AC output:

Code: Select all

```
0.0 0.0 0.0
0.0 0.0 0.0
0.0 0.0 1.0
0.0 0.0 1.0
```

Code: Select all

```
(0.000,0.000)
THE CIRCLES ARE THE SAME
```

Posted: **Mon Jul 25, 2016 6:32 pm**

Another problem tricky float point number involved.

Posted: **Sat Feb 03, 2018 8:08 am**

I think the test cases for this problem actually uncover literally every precision problem that you can have with floating point numbers.

NaNs from**subtracting **two non-NaN floats, negative 0's...this was quite a party!

Also, remember that a point is a degenerate circle.

So, you have to cover the case where you have one zero radius circle that sits on the other circle's border.

And, you have to cover the case where two 0 radius circles have the same "center" - this case still has a single intersection.

I can say my geo libraries are much improved after this one!

NaNs from

Also, remember that a point is a degenerate circle.

So, you have to cover the case where you have one zero radius circle that sits on the other circle's border.

And, you have to cover the case where two 0 radius circles have the same "center" - this case still has a single intersection.

I can say my geo libraries are much improved after this one!

Posted: **Mon Oct 01, 2018 4:21 pm**

Why? are they intersect? or this is a special case?ujjal.ruet wrote: ↑Thu Nov 11, 2010 10:00 amgootsa,please check this testcase..

please ,send your new code to me,if you dont mind....Code: Select all

`input 1.0 1.0 5.0 1.0 1.0 10.0 output must be (1.000,1.000)`

usuttra@yahoo.com