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

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Fri Jul 07, 2006 10:08 pm

hey ,
can you gimme your source code. I just wanna compare it with mine. my email address is niklaus@gmail.com

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple » Fri Nov 24, 2006 5:29 am

I get the same output which adrian posted but still WA.
Who can help me?Point out my fault.thanks!
The following is my code:

Code: Select all

ACed at last
Last edited by pineapple on Mon Apr 30, 2007 5:21 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Nov 24, 2006 10:09 am

Its really tough to get this one accepted. And finding bug is impossible. Try changing these...

Code: Select all

if(ar-br==0.0)
Dont use this, try to use
if( fabs(ar-br) < eps )
And eps should be positive and small. 1e-7 or 1e-8 will do. Try changing these.
Ami ekhono shopno dekhi...
HomePage

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

453 PE

Post by jurajz » Mon Feb 26, 2007 12:31 am

Many threads to this problem are about Wrong Answer. My first submit was WA too, but next 4 submissions I had PE. I don't understand, why :(

I think, that messages ("NO INTERSECTION" or "THE CIRCLES ARE THE SAME") and coordinates of the points (with parenthesis) I print correct, without any blanks. I think about extra lines in the end of input. I avoid to write "-0.000", I write "0.000". But still PE. Blank lines shouldn't be here...

Have someone idea, where may be the reason of PE? Many solution have PE in this problem. {198 AC/ 145 PE in this time}

Thanks in advance!

Please sorry for my bad english.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Feb 26, 2007 1:57 pm

I got PE several times, too. Then I changed the 'eps' value and got accepted.
Ami ekhono shopno dekhi...
HomePage

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Post by jurajz » Mon Feb 26, 2007 9:17 pm

Many thanks, Jan. After 6 PE I got Accepted. You are right, PE is caused by EPS value. For 10^( -12 ) or 10^( -8 ) it is PE. For 10^( -4 ) it is AC.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Thu May 03, 2007 10:00 pm

I've tried with Epsilon = 1e-4 and 1e-8 and got PE in both cases.
What might be wrong?
The PE ratio is also quite high.
This problem has a special corrector (probably because of the accuracies?)

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

453 WA

Post by likhan » Sat Jun 09, 2007 12:55 pm

Everybody is talking about getting PE, but man I cannot remove WA talk about PE later. Anyways looked for Adrian's inputs, but they are not any more available neither from Stefen site nor Adrians. Somebody please come to rescue, I'm going crazy already tried arnd 20 submissions with different combinations. Heeeeeeeeeelllllllllpppppppppp.

Code: Select all

#include <stdio.h>
#include <math.h>

#define EPS 1e-4
#define EQUAL(a,b) (fabs((a)-(b))<EPS)
#define ROUND(a) ((long)(((a)+5e4)*1000))
#define SQR(a) ((a)*(a))
#define ZERO(a) (fabs(a)<EPS)

void main()
{
	double x1, y1, r1, x2, y2, r2, D, A, ix1, iy1, ix2, iy2;

	//freopen("453.in", "r+", stdin);

	//printf("%lf", EPS);

	while ( scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &r1, &x2, &y2, &r2) == 6 )
	{
		D = SQR(x1 - x2) + SQR(y1 - y2);
		D = sqrt(D);
		A = (D + r1 + r2) * (D + r1 - r2) * (D - r1 + r2) * (-D + r1 + r2);

		if ( EQUAL(x1, x2) && EQUAL(y1, y2) && EQUAL(r1, r2) )
		{
			puts("THE CIRCLES ARE THE SAME");
		}
		else if (D < fabs(r1 - r2) || D > (r1 + r2) )
		//else if ((r1 + r2) < D )
		{
			puts("NO INTERSECTION");
		}
		else
		{
			A = (sqrt(A) / 4.0);
			ix1 = ix2 = ((x1 + x2) / 2) - (((x1 - x2) * (SQR(r1)-SQR(r2))) / (2 * SQR(D)));
			ix1 = ix1 + ((2 * (y1 - y2) * A) / SQR(D));
			ix2 = ix2 - ((2 * (y1 - y2) * A) / SQR(D));

			iy1 = iy2 = ((y1 + y2) / 2) - (((y1 - y2) * (SQR(r1)-SQR(r2))) / (2 * SQR(D)));
			iy1 = iy1 - ((2 * (x1 - x2) * A) / SQR(D));
			iy2 = iy2 + ((2 * (x1 - x2) * A) / SQR(D));

			ix1 = (ZERO(ix1) ? 0 : ix1);
			iy1 = (ZERO(iy1) ? 0 : iy1);
			ix2 = (ZERO(ix2) ? 0 : ix2);
			iy2 = (ZERO(iy2) ? 0 : iy2);

			//if ( ROUND(ix1) == ROUND(ix2) && ROUND(iy1) == ROUND(iy2) )
			if ( EQUAL(ix1, ix2) && EQUAL(iy1, iy2) )
			{
				printf("(%.3lf,%.3lf)\n", ix1, iy1);
			}
			else
			{
				if ( (ix1 < ix2) || (EQUAL(ix1, ix2) && (iy1 < iy2)) )
					printf("(%.3lf,%.3lf)(%.3lf,%.3lf)\n", ix1, iy1, ix2, iy2);
				else
					printf("(%.3lf,%.3lf)(%.3lf,%.3lf)\n", ix2, iy2, ix1, iy1);
			}
		}
	}
}

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by kn » Wed Jun 20, 2007 9:55 pm

Really tough problem...
My code passed the test case provided by the other post...yet, WA

Round-off problem is difficult to tackle... for this online judge.
I think dealing with the round-off error "correctly" requires some "luck".

BTW, why I can't search the posts of this problem after I entered "453"?

Code: Select all

#include <iostream>
#include <cstdio>
#include <math.h>
#define EPSILON 1e-4

using namespace std;

double xc1, xc2, yc1, yc2;
double r1, r2;

inline bool EQUAL(double X, double Y){
	return fabs(X-Y)<EPSILON;
}

inline double zz(double X){
	if(fabs(X)<EPSILON)	return 0.000;
	else	return X;
}

void printPair(double X, double Y);

int main(){
	while(scanf("%lf", &xc1)!=EOF){
		scanf("%lf %lf", &yc1, &r1);
		scanf("%lf %lf %lf", &xc2, &yc2, &r2);
	
		if(EQUAL(xc1,xc2) && EQUAL(yc1,yc2) && EQUAL(r1,r2)){
			if(EQUAL(r1,0.000)&&EQUAL(r2,0.000))
				printf("(%.3lf,%.3lf)\n",xc1,yc1);
			else
				printf("THE CIRCLES ARE THE SAME\n");
			continue;
		}

		double dx = xc1-xc2;
		double dy = yc1-yc2;
		double sqD = dx*dx+dy*dy;
		double sumR = r1+r2;
		double sqSumR = sumR*sumR;
		double diffR = r1-r2;
		double sqDiffR = diffR*diffR;
	
		if(EQUAL(sqD,sqSumR)){
			// Touch externally
			// Exactly 1 intersecting pt
			double ratio = r2/sumR;
			printPair(xc2+dx*ratio, yc2+dy*ratio);
			printf("\n");
		}else{
			// Find Equation of Chord...
			double d1=-2*xc1, e1=-2*yc1, f1=xc1*xc1+yc1*yc1-r1*r1;
			double d2=-2*xc2, e2=-2*yc2, f2=xc2*xc2+yc2*yc2-r2*r2;
			double A=d1-d2, B=e1-e2, C=f1-f2;
			double xFinal, yFinal;
			
			// Touches internally
			// Exactly 1 intersectin pt
			if(EQUAL(sqD,sqDiffR)){
				if(EQUAL(B,0.000)){
					xFinal = -C/A;
					yFinal = yc1;
				}else{
					double AoverB = A/B, CoverB = C/B;
					double a=1+AoverB*AoverB;
					double b=-2*xc1+2*AoverB*(yc1+CoverB);
					xFinal = -b/2/a;
					yFinal = -AoverB*xFinal - CoverB;
				}
				printPair(xFinal, yFinal);
				printf("\n");
			}else if(sqD > sqSumR || sqD < sqDiffR){
				// No intersection
				printf("NO INTERSECTION\n");
			}else{
				// Distinct intersections
				if(EQUAL(B,0.000)){
					printf("EQUAL B, DISTINCT\n");
					
					xFinal = -C/A;
					double temp=xFinal-xc1;
					double c=r1*r1-temp*temp;
					double rDelta=sqrt(c);
					printPair(xFinal, yc1-rDelta);
					printPair(xFinal, yc1+rDelta);
				//	printf("(%.3lf,%.3lf)\n", zz(xFinal), yc1+rDelta);
				}else{
					double AoverB = A/B, CoverB = C/B;
					double a=1+AoverB*AoverB;
					double b=-2*xc1+2*AoverB*(yc1+CoverB);
					double temp=CoverB+yc1;		temp*=temp;
					double c=xc1*xc1+temp-r1*r1;
					double DELTA = b*b-4*a*c;
					double rDelta = sqrt(DELTA);
					xFinal = (-b-rDelta)/2/a;
					yFinal = -AoverB*xFinal - CoverB;
					printPair(xFinal, yFinal);
					
					xFinal = (-b+rDelta)/2/a;
					yFinal = -AoverB*xFinal - CoverB;
					printPair(xFinal, yFinal);
				}
				printf("\n");
			}
		}
	}
	return 0;
}

void printPair(double X, double Y){
	printf("(%.3lf,%.3lf)", zz(X), zz(Y));
}

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 453 argghhh

Post by zobayer » Sun Nov 07, 2010 12:23 pm

those who are still in trouble with this one: just make sure your formula is correct (no matter what you see in your pc)

I used eps = 1e-4
carefully compare:
a > b should be a > b + eps
a < b should be a + eps < b
a == b should be fabs(a - b) < eps

for comparing if there is only one point, calculate two points as usual, then compare if they are same, don't use any other properties for checking if they are same, and don't forget to maintain the order. remember also that, there are circles of 0.00 radii.

before submitting, make eps = 1e-4
I got PE with 1e-5 and AC with 1e-4, although, in my pc, 1e-4 produces many incorrect answer where 1e-5 produces more correct answers (according to IO provided with in this thread). got ac in 3 submissions... :D

nice geometry with frustrating IO set.
You should not always say what you know, but you should always know what you say.

ujjal.ruet
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh
Contact:

Re: 453

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

ujjal.ruet
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh
Contact:

Re: 453 argghhh

Post by ujjal.ruet » Thu Nov 11, 2010 1:04 pm

I got AC on this problem.

check this test case given below.U will get AC also...

Code: Select all

1.0 1.0 5.0
1.0 1.0 5.0
1.0 1.0 0.0
1.0 1.0 0.0
5.2 2.5 0.0
6.1 8.2 0.0

gootsa
New poster
Posts: 9
Joined: Sat Jun 25, 2005 9:26 am

Re: 453

Post by gootsa » Thu Nov 11, 2010 1:50 pm

But why the answer should be (1,1)? These two circles does not have any intersection.

h.hesham
New poster
Posts: 1
Joined: Sun Aug 05, 2012 6:56 am

Re: 453 PE

Post by h.hesham » Sun Aug 05, 2012 7:00 am

Code: Select all

if(EQUAL(xc1,xc2) && EQUAL(yc1,yc2) && EQUAL(r1,r2))
your problem is here, an infinite number of points does not mean that they MUST be the same (although the output says so)

Shadek
New poster
Posts: 2
Joined: Thu Sep 05, 2013 2:23 pm

453: Query

Post by Shadek » Sun Sep 15, 2013 4:22 am

Why the output for the following input is "NO INTERSECTION"?

Code: Select all

0.931547 0.869930 0.866543
0.674520 0.758415 0.581896
Can anybody prove mathematically?

I see distance of two centers is 0.280176, some of two radius is 1.44844. So there should be intersections.

Post Reply

Return to “Volume 4 (400-499)”