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

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

About 453.

Post by Zuberul » Fri Nov 26, 2004 10:39 pm

Hi
what is the problem with this one.
I am getting continous WA.
my algo...

checked whether they are on straight line or not.
then checked whether they are touching (both internaly or externaly)
then

1. find the eqn of the common chord
2.find the eqn of the line joining the centers
3.got the intersecting point
4.find the tangent of the line joining the intersect point and any of the centre
5.find the horizontal & vertical distance
6.added with the intersecting point after mult by sin or cos of tangent
7.rounded them & print them.

I read the previous posts found a link to a large input set & tested it
got the same result with no precession error.

is this only due to precession error?
what should i do?

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

453 wa ,, need some input and output sample

Post by sunnycare » Thu Mar 31, 2005 8:20 am

i think this problem is very easy.....but i got WA again and again.....

i dont know .....

who can give me some input and output smaple..??

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;

void main()
{
	double a1,b1,c1;
	double a2,b2,c2;

	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(3);
	
	double A,B;
	double x1,y1;
	double x2,y2;
	double tmp;
	while(cin>>a1)
	{
		cin>>b1>>c1>>a2>>b2>>c2;
		if(a1==a2)
		{
			if(b1==b2)
			{
				if(c1==c2)
				{
					cout<<"THE CIRCLES ARE THE SAME"<<endl;
				}
				else
				{
					cout<<"NO INTERSECTION"<<endl;
				}
			}
			else
			{
				y1=(c1*c1-c2*c2-b1*b1+b2*b2)/(2*(b2-b1));
				tmp=c1*c1-(y1-b1)*(y1-b1);
				tmp=sqrt(tmp);
				if(tmp==0)
				{
					x1=a1;
					cout<<'('<<x1<<','<<y1<<')'<<endl;
				}
				else
				{
					x1=a1-tmp;
					x2=a1+tmp;
					cout<<'('<<x1<<','<<y1<<')';
					cout<<'('<<x2<<','<<y1<<')'<<endl;
				}
			}

		}
		else
		{
			A=(b2-b1)/(a2-a1);
			B=(c1*c1-c2*c2+b2*b2+a2*a2-a1*a1-b1*b1)/(2*(a2-a1));
			double u,v,w;
			u=A*A+1;
			v=2*(A*(B-a1)-b1);
			w=((B-a1)*(B-a1)+b1*b1-c1*c1);

			double delta=v*v-4*u*w;
			if(delta==0)
			{
				y1=-v/(2*u);
				x1=A*y1+B;
				cout<<'('<<x1<<','<<y1<<')'<<endl;
			}
			else
			{
				if(delta<0)
					cout<<"NO INTERSECTION"<<endl;
				else
				{
					delta=sqrt(delta);
					y1=(-v-delta)/(2*u);
					y2=(-v+delta)/(2*u);
					x1=A*y1+B;
					x2=A*y2+B;
					if(x1<x2)
					{
						cout<<'('<<x1<<','<<y1<<')';
						cout<<'('<<x2<<','<<y2<<')'<<endl;
					}
					else
					{
						if(x1==x2)
						{
							if(y1<y2)
							{
								cout<<'('<<x1<<','<<y1<<')';
								cout<<'('<<x2<<','<<y2<<')'<<endl;
							}
							else
							{
								cout<<'('<<x2<<','<<y2<<')';
								cout<<'('<<x1<<','<<y1<<')'<<endl;
							}
						}
						else
						{
							cout<<'('<<x2<<','<<y2<<')';
							cout<<'('<<x1<<','<<y1<<')'<<endl;
						}
					}
				}
			}
		}
	}
}

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

453 - Intersecting Circles

Post by Antonio Ocampo » Tue May 03, 2005 2:08 am

Hi fellows

I got several WA. Would you mind giving me any critical I/O ?

Thx in advance :D

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun May 15, 2005 10:39 pm

Please help me!! :cry:

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue May 17, 2005 3:45 pm


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

453

Post by gootsa » Sat Jun 25, 2005 9:33 am

I got so much wrong answer for this problem,
I read the pervios message about this problem, but it can't help me, :(
( I creat a new because those did'nt found whit search :o )

please help me,

Code: Select all

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;

//ifstream fin("in.txt");
//ofstream fout("out.txt");
//#define cin fin
//#define cout fout
#define EPS 1e-4

bool eq(double a, double b)
{	return fabs(a-b)<EPS;	}
bool ne(double a, double b)
{	return fabs(a-b)>=EPS;	}
bool lt(double a, double b)
{	return b-a>=EPS;	}
bool gt(double a, double b)
{	return a-b>=EPS;	}
bool le(double a, double b)
{	return b-a>-EPS;	}
bool ge(double a, double b)
{	return a-b>-EPS;	}


double round(double a)
{
	if(lt(a,0))
	{
		a=-a;
		return -floor(a*1000+0.5)/1000;
	}
	return floor(a*1000+0.5)/1000;
}

struct Point
{
	double x,y;
	Point (double _x=0, double _y=0)
		:x(_x), y(_y){}
	bool operator<(Point p)
	{
		if(ne(p.x,x))
			return lt(x,p.x);
		return lt(y,p.y);
	}
	bool operator==(Point p)
	{
		return eq(p.x,x)&&eq(p.y,y);
	}
};
struct Circle
{
	Point c;
	double r;
	Circle(Point _c=Point(0,0), double _r=0):c(_c),r(_r)
	{
	}
};

#define sq(a) ((a)*(a))
double Distance(Point p1, Point p2)
{
	return sqrt(sq(p1.x-p2.x)+sq(p1.y-p2.y));
}

void rotate(Point o, Point & p, double Sin, double Cos)
{
	p.x-=o.x;
	p.y-=o.y;
	double tx = p.x * Cos - p.y * Sin;
	double ty = p.x * Sin + p.y * Cos;
	p.x = tx + o.x;
	p.y = ty + o.y;
}

double triangleArea(double a, double b,double c)
{
	double s=(a+b+c)/2;
	return sqrt(s*(s-a)*(s-b)*(s-c));
}

int circle_circle_intersection(Circle c1,Circle c2, Point & p1, Point & p2)
{
	double d=Distance(c1.c, c2.c);
	
	if(gt(d,c1.r+c2.r)||gt(fabs(c1.r-c2.r),d))
		return 0;//circles don't intersect
	
	if(eq(d,0))
			return 3;//circles are the same
	if(lt(c1.r,c2.r))
		swap(c1,c2);
	double x,y;
	x=c1.c.x+(c2.c.x-c1.c.x)*c1.r/d;
	y=c1.c.y+(c2.c.y-c1.c.y)*c1.r/d;
	
	p1=p2=Point(x,y);

	if( eq(c1.r+c2.r,d) || eq(fabs(c1.r-c2.r),d))
		return 1;//circles are tangent 
	
	double h=triangleArea(c1.r,c2.r,d)*2/d;
	
	double Sin,Cos;
	Sin=h/c1.r;
	Cos=sqrt(fabs(1-sq(Sin)));
	
	rotate(c1.c, p1, Sin, Cos);
	rotate(c1.c, p2,-Sin, Cos);
	return 2;
}

void print(double a)
{
	cout.setf(ios::fixed|ios::showpoint);
	cout.precision(3);
	if(eq(a,0))
		cout<<"0.000";
	else
		cout<<a;
}

int main()
{
	Circle c1,c2;
	Point p1,p2;
	while(cin>>c1.c.x>>c1.c.y>>c1.r>>c2.c.x>>c2.c.y>>c2.r)
	{
		int a=circle_circle_intersection(c1,c2,p1,p2);
		if(a==2)
		{
			if(p2<p1)
				swap(p2,p1);
			p2.x=round(p2.x);
			p1.x=round(p1.x);
			p2.y=round(p2.y);
			p2.x=round(p2.x);
			if(p2==p1)
				a=1;
		}
		if(a==3)
			cout<<"THE CIRCLES ARE THE SAME"<<endl;
		else if(a==1)
		{
				cout<<"(";print(p1.x);cout<<",";print(p1.y);cout<<")"<<endl;
		}
		else if(a==2)
		{
				cout<<"(";print(p1.x);cout<<",";print(p1.y);cout<<")(";
				print(p2.x);cout<<",";print(p2.y);cout<<")"<<endl;
		}
		else
			cout<<"NO INTERSECTION"<<endl;

	}
	return 0;
}

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Sat Jun 25, 2005 7:04 pm


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

Post by gootsa » Sun Jun 26, 2005 6:32 am

I set EPSILON = 1e-4 and my out put for the test case that says about are all right , but I still get WA,
Please help me,

Code: Select all


#include <iostream> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <fstream> 
using namespace std; 

//ifstream fin("in.txt"); 
//ofstream fout("out.txt"); 
//#define cin fin 
//#define cout fout 
#define EPS 1e-4 

bool eq(double a, double b) 
{   return fabs(a-b)<EPS;   } 
bool ne(double a, double b) 
{   return fabs(a-b)>=EPS;   } 
bool lt(double a, double b) 
{   return b-a>=EPS;   } 
bool gt(double a, double b) 
{   return a-b>=EPS;   } 
bool le(double a, double b) 
{   return b-a>-EPS;   } 
bool ge(double a, double b) 
{   return a-b>-EPS;   } 


double round(double a) 
{ 
   if(lt(a,0)) 
   { 
      a=-a; 
      return -floor(a*1000+0.5)/1000; 
   } 
   return floor(a*1000+0.5)/1000; 
} 

struct Point 
{ 
   double x,y; 
   Point (double _x=0, double _y=0) 
      :x(_x), y(_y){} 
   bool operator<(Point p) 
   { 
      if(ne(p.x,x)) 
         return lt(x,p.x); 
      return lt(y,p.y); 
   } 
   bool operator==(Point p) 
   { 
      return eq(p.x,x)&&eq(p.y,y); 
   } 
}; 
struct Circle 
{ 
   Point c; 
   double r; 
   Circle(Point _c=Point(0,0), double _r=0):c(_c),r(_r) 
   { 
   } 
}; 

#define sq(a) ((a)*(a)) 
double Distance(Point p1, Point p2) 
{ 
   return sqrt(sq(p1.x-p2.x)+sq(p1.y-p2.y)); 
} 

void rotate(Point o, Point & p, double Sin, double Cos) 
{ 
   p.x-=o.x; 
   p.y-=o.y; 
   double tx = p.x * Cos - p.y * Sin; 
   double ty = p.x * Sin + p.y * Cos; 
   p.x = tx + o.x; 
   p.y = ty + o.y; 
} 

double triangleArea(double a, double b,double c) 
{ 
   double s=(a+b+c)/2; 
   return sqrt(s*(s-a)*(s-b)*(s-c)); 
} 

int circle_circle_intersection(Circle c1,Circle c2, Point & p1, Point & p2) 
{ 
   double d=Distance(c1.c, c2.c); 
    
   if(gt(d,c1.r+c2.r)||gt(fabs(c1.r-c2.r),d)) 
      return 0;//circles don't intersect 
    
   if(eq(d,0)) 
         return 3;//circles are the same 
   if(lt(c1.r,c2.r)) 
      swap(c1,c2); 
   double x,y; 
   x=c1.c.x+(c2.c.x-c1.c.x)*c1.r/d; 
   y=c1.c.y+(c2.c.y-c1.c.y)*c1.r/d; 
    
   p1=p2=Point(x,y); 

   if( eq(c1.r+c2.r,d) || eq(fabs(c1.r-c2.r),d)) 
      return 1;//circles are tangent 
    
   double h=triangleArea(c1.r,c2.r,d)*2/d; 
    
   double Sin,Cos; 
   Sin=h/c1.r; 
   Cos=sqrt(fabs(1-sq(Sin))); 
    
   rotate(c1.c, p1, Sin, Cos); 
   rotate(c1.c, p2,-Sin, Cos); 
   return 2; 
} 

void print(double a) 
{ 
   cout.setf(ios::fixed|ios::showpoint); 
   cout.precision(3); 
   if(eq(a,0)) 
      cout<<"0.000"; 
   else 
      cout<<a; 
} 

int main() 
{ 
   Circle c1,c2; 
   Point p1,p2; 
   while(cin>>c1.c.x>>c1.c.y>>c1.r>>c2.c.x>>c2.c.y>>c2.r) 
   { 
      int a=circle_circle_intersection(c1,c2,p1,p2); 
      if(a==2) 
      { 
         if(p2<p1) 
            swap(p2,p1); 
         p2.x=round(p2.x); 
         p1.x=round(p1.x); 
         p2.y=round(p2.y); 
         p2.x=round(p2.x); 
         if(p2==p1) 
            a=1; 
      } 
      if(a==3) 
         cout<<"THE CIRCLES ARE THE SAME"<<endl; 
      else if(a==1) 
      { 
            cout<<"(";print(p1.x);cout<<",";print(p1.y);cout<<")"<<endl; 
      } 
      else if(a==2) 
      { 
            cout<<"(";print(p1.x);cout<<",";print(p1.y);cout<<")("; 
            print(p2.x);cout<<",";print(p2.y);cout<<")"<<endl; 
      } 
      else 
         cout<<"NO INTERSECTION"<<endl; 

   } 
   return 0; 
} 

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

Post by gootsa » Sun Jun 26, 2005 6:32 am

I saw that post , but it coudn't help me :(

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Sun Jun 26, 2005 6:55 pm

I reember, there is a link to some test data for this problem. Try them.

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

Post by gootsa » Sun Jun 26, 2005 10:02 pm

my program produce right out put for those test,
but I get WA :(

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Accepted

Post by Moha » Sat Oct 29, 2005 3:08 am

At last, I got accepted!
this test case, revealed my bug:
0 0 0
1 0 1
answer should be
(1.000,0.000)
with sepcial thanks to Yury Khol.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Jan 06, 2006 11:05 am

Funny thing that you can't get any hits if you search for 453... roundingerror? :)

Anyway, does anyone have this big input file with correct output still sitting around on their hard drive? I'm going crazy with this thing.

Oh, and how is that correct output (the post above)?
Shouldn't
0 0 0
1 0 1
give
(0.000,0.000)?
My program prints (1.000,0.000) for
0 0 1
1 0 0

here's few, can someone at least run these through?

Code: Select all

0.0 0.0 1.0
3.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
1.0 0.0 1.0
0.0 0.0 2.0
0.0 1.0 1.0
0.0 0.0 2.0
0.0 1.0 0.5
0.0 0.0 2.0
0.0 3.0 1.0
0.0 0.0 2.0
0.0 3.0 0.9999999
0.0 0.0 2.0
0.0 3.0 0.99999999
0.0 0.0 5.0
6.0 8.0 5.0
1.1 1.1 4.0
2.2 2.2 3.0
3.3 4.4 1.9
2.5 3.7 1.7
1.2 3.4 5.6
6.5 3.2 4.8
-1.2 -3.4 5.6
0.0 0.0 2.0
0.0 0.0 7.0
0.0 4.0 11.0
1.4 -2.5 2.5 
-5.4 4.6 8.2
1.0 1.0 0.0 
1.0 1.0 0.0
0 0 0 
1 0 1
0 0 1 
1 0 0
0.0 0.0 2.0 
0.0 0.0 1.0
My output:

Code: Select all

NO INTERSECTION
THE CIRCLES ARE THE SAME
(0.500,-0.866)(0.500,0.866)
(0.000,2.000)
NO INTERSECTION
(0.000,2.000)
(0.000,2.000)
(0.000,2.000)
(3.000,4.000)
(1.393,5.089)(5.089,1.393)
(1.533,5.098)(3.757,2.556)
(4.467,-1.148)(4.801,7.689)
(0.488,1.940)(0.838,1.816)
(0.000,-7.000)
(-1.097,-2.380)(1.388,0.000)
THE CIRCLES ARE THE SAME
(0.000,0.000)
(1.000,0.000)
NO INTERSECTION
Note that 7th and 8th line depend heavily on EPS. This is the output for EPS = 1e-4. I tried everything from 1e-3 to 1e-15.

Darko

cycos83
New poster
Posts: 2
Joined: Wed Jan 18, 2006 10:42 am

453 give me some input & output please

Post by cycos83 » Wed Jan 18, 2006 10:45 am

my program is WA help me

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

A question about ACM 453

Post by Wei-Ming Chen » Tue May 02, 2006 5:01 pm

I got WA in this problem.
I checked discussing board and saw some people use "1E-4" and got AC
I knew 1E-4=0.0001 , but I didn't know how to use it on this problem.
Is my code only have to check the input to precise 1E-4 ?
(If two number a , b , |a-b|<=1E-4 , they are same?)
Can someone tell me? Thanks.

Post Reply

Return to “Volume 4 (400-499)”