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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 453: Intersecting Circles

Post by brianfry713 » Sun Sep 15, 2013 4:39 am

Image
One circle is inside the other.
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 453 - Intersecting Circles

Post by Shahidul.CSE » Tue Jan 13, 2015 12:14 pm

Getting WA. But why? My code passes all the input on this forum.
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;
}
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 453 - Intersecting Circles

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 453 - Intersecting Circles

Post by Shahidul.CSE » Wed Jan 14, 2015 11:45 am

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

And how to determine when to use which value for EPS? Because it is so sensitive in programming contest.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 453 - Intersecting Circles

Post by brianfry713 » 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/
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 453 - Intersecting Circles

Post by Shahidul.CSE » Thu Jan 15, 2015 7:04 am

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/
Even getting WA!
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;
}
And with previous code, I got correct outputs for all the test cases posted on this forum. But with the above code, I got wrong outputs for several test cases. Such as, I got output 0.087 instead of 0.086
So, what to do?
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 453 - Intersecting Circles

Post by brianfry713 » Fri Jan 16, 2015 2:07 am

Input:

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
AC output:

Code: Select all

(0.000,0.000)
THE CIRCLES ARE THE SAME
Check input and AC output for thousands of problems on uDebug!

metaphysis
Experienced poster
Posts: 129
Joined: Wed May 18, 2011 3:04 pm

Re: 453 - Intersecting Circles

Post by metaphysis » Mon Jul 25, 2016 6:32 pm

Another problem tricky float point number involved.

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 453 - Intersecting Circles

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

NAbdulla
New poster
Posts: 31
Joined: Wed Jul 30, 2014 3:40 pm
Contact:

Re: 453

Post by NAbdulla » Mon Oct 01, 2018 4:21 pm

ujjal.ruet wrote:
Thu Nov 11, 2010 10:00 am
gootsa,please check this testcase..

Code: Select all

input
1.0 1.0 5.0
1.0 1.0 10.0

output must be
(1.000,1.000)



please ,send your new code to me,if you dont mind....
usuttra@yahoo.com
Why? are they intersect? or this is a special case?

Post Reply

Return to “Volume 4 (400-499)”