CIRCLES2 - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Rami

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Geometry, Trigonometry.

PROBLEM:

Given two circles P1 with centre A(x1, y1) and radius r1 and P2 with centre B(x2, y2) and radius r2. Determine whether there exists a point P which lies inside, or at border of P1, but strictly outside P2, and find such point.

EXPLANATION

By definition of circle, we want to find a point P such that distance between P and A(x1, y1) is less than or equal to r1 and distance from B(x2, y2) is greater than r2.

Thus, we need to point within first circle, which is farthest from centre of second circle. We can see, if that point lies within second circle, first circle lies within second circle, and there doesn’t exist any such point. Let’s call this best point.

We can see, that since the best point need to be as far as possible from B, it’s best to move directly in opposite direction starting from A till we reach the permieter of circle P1. Let’s Call this point C(x3, y3).

People say a picture is worth 1000 words, so, attaching one. :stuck_out_tongue:
circles2

Proof this point is optimal, is below.

Suppose point D(x4, y4) is the optimal point, which is not same as C and lies on perimeter. We can see, that a non-degenerate triangle formed by points A, point B and point D. Using triangle inequality, we can see that dist(D, B) < dist(D, A)+dist(A, B). But for point C, we have dist(C, B) = dist(C, A)+dist(A, B) which proves that point C is more distant from B than any other point D.

Now, let’s calculate point C. We know, it lies on line formed by points A and B. So, we can find the slope as well as equation of line using two point form. We also have equation of first circle, solving them gives us this point (and one other point, we need to be careful). But there’s a simpler way.

Let’s consider θ being the angle formed by line AB as shown by yellow arc in image. Consider a right triangle whose base and perpendicular are parallel to x-axis and y-axis respectively and whose hypotenuse is AC. Length of AC is r1. It can be seen, that we can find the length of base and perpendicular using trigonometry (base is r1*cos(θ) and perpendicular is r1*sin(θ)). This allows us to calculate coordinates of C.

Final check, if the distance between B and C is strictly greater than r2, C is our required point, otherwise no such point exists.

If the centres of both circles coincide, It is easy to see, that answer exists, if r1 > r2 and any point C can also be easily calculated.

Bonus:

Is there any simpler method, if we were to answer only YES/NO and not the point (without calculating the point)?

There may be many related problems, try using geometry tag on problems at SPOJ, Codeforces.

TIME COMPLEXITY

Time complexity is O(1) per test case.

SOLUTIONS:

Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

#define int ll
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int x1,y1,x2,y2,r1,r2;
		cin>>x1>>y1>>r1>>x2>>y2>>r2;
		int dist2=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
		if(r1>r2 || (dist2>(r2-r1)*(r2-r1))){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
			continue;
		}
		long double dist=sqrt((double)dist2);
		if(dist2==0){
			cout<<x1+r1<<" "<<y1<<endl;
		}
		else{
			cout<<setprecision(30)<<(x1*(dist+r1)-r1*x2)/dist;
	        cout<<" ";
	        cout<<setprecision(30)<<(y1*(dist+r1)-r1*y2)/dist<<endl;
		}
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CIRCLES2{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    double x1 = nd(), y1 = nd(), r1 = nd(), x2 = nd(), y2 = nd(), r2 = nd();
	    if(x1 == x2){
	        if(y1 == y2){
	            //Same centres
	            if(r1 <= r2)pn("NO");
	            else {
	                //Any point on perimeter of first circle is valid
	                pn("YES");
	                print(x1+r1, y1);
	            }
	        }else{
	            if(y1 < y2){
	                if(y1-r1 < y2-r2){
	                    pn("YES");
	                    print(x1, y1-r1);
	                }else pn("NO");
	            }else{
	                if(y1+r1 > y2+r2){
	                    pn("YES");
	                    print(x1, y1+r1);
	                }else pn("NO");
	            }
	        }
	    }else{
	        double theta = Math.atan2(y2-y1, x2-x1);
	        double x3 = x1-r1*Math.cos(theta), y3 = y1-r1*Math.sin(theta);
	        if(dist(x3, y3, x2, y2) - r2 > eps){
	            pn("YES");
	            print(x3, y3);
	        }else pn("NO");
	    }
	}
	double dist(double x1, double y1, double x2, double y2){
	    return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	}
	void print(double x, double y){
	    pn(df.format(x)+" "+df.format(y));
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	double eps = 1e-7;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new CIRCLES2().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

3 Likes

@taran_1407 or anyone can please let me know what’s the error in my solution. I spent almost 2 hours on this solution but couldn’t find the bug.

The logic is same as mentioned in the editorial.

link to the solution

I spent also 2 hours for this question. I thought that was a math question, but not… it’s just a matter of precision:

I got WA when I do : cout.precision(10);

and now AC with : cout.precision(40);

In the statement, it said that precision is needed up to 10^{-6}, but it is misleading during the contest… It’s a pity…

3 Likes

try
cout<<fixed;
cout.precision(10);

you should get AC.

3 Likes

I felt like this solution could be solved using mid point circle algorithm?
@taran_1407

1 Like

Hello… I also solved the question with the exact same approach…

Please can you tell me what leads it to WA…
link : https://www.codechef.com/viewsolution/26017329

Code Explanation :
the function outside returns whether the point p is outside the circle 2 or not

p1 and p2 are the two points that lie on the circumference of circle 1 and are intersection points of circle 1 and line joining centres of both circles…

I am trying that if anyone of those points is outside the circle 2 - then I say yes and print those co-ordinates… ( using print function )

also precision = 12 ; so maybe that should not be the issue… ( defined in macro in # define pp )

line stands for new line ( cout << ‘\n’ ; )

Please help… thanks in advance…!

in EXAMPLE test case : 0 1 1 0 2 2
if we take point 0,0 then its distance from 0,1 is <=1+10^-6 and it distance from 0,2 is >=2-10^-6 then why it is not considered into the answer?? a NO is mentioned there?? please explain somebody

Hi sir, I also faced the same problem yesterday. The only error that I can think of in this solution is that you are using setprecision only while printing the answer. Thus the conditions on line 130 and 138 may be evaluated incorrectly due to the precision mistakes of h. Could you please try using setprecision at the starting of the program and let me know if it worked🙂

Although I couldn’t find anything wrong in your solution. There is something I would like to point out. You are comparing 2 floating point numbers using the equality operator. Doing this can get you in trouble in a lot of situations since floating point numbers may not compare equal using == even if they might be equal. This is because of precision issues. Better use something like abs(a - b) < EPS, where EPS is something like 1e-9.

Even that doesn’t work. link

The problem must be related to double errors. Eg 123456789012345 will be stored as 1.23457e14 which is equal to (123457000000000).

P.S. This problem increased my fear of using double :pensive:

1 Like

I think your code will work with precision equal to 10 as well.

Use a fixed keyword before setting precision

Like this,

cout<<fixed;

Yeahhh…muje bhi lga…par implement nhi kr paaya

1 Like

When this type of condition occur, use printf(%.10f",x) more precise and correct

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. /
class codechef
{
public static double distance(int x1,int y1,int x2,int y2)
{
double d=Math.sqrt(((x1-x2)
(x1-x2))+((y1-y2)*(y1-y2)));
return d;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++)
{

		int x1=sc.nextInt();
		int y1=sc.nextInt();
		int r1=sc.nextInt();
		int x2=sc.nextInt();
		int y2=sc.nextInt();
		int r2=sc.nextInt();
		if(distance(x1,y1,x2,y2)<=(r2-r1))
			System.out.println("NO");
		else if(distance(x1,y1,x2,y2)<=r2)
		{
		  double X=(((distance(x1,y1,x2,y2)+r1)*x1)-(r1*x2))/(distance(x1,y1,x2,y2));
		  double Y=(((distance(x1,y1,x2,y2)+r1)*y1)-(r1*y2))/(distance(x1,y1,x2,y2));
		  System.out.println("YES");
		  System.out.println(X+" "+Y);
		}
		else
		{
			System.out.println("YES");
			System.out.println((double)x1+" "+(double)y1);
		}
	}

	// your code goes here
}

}
Please Help me to find error with this approach.

I have solved it vectorially.

First, find the relative position of the centre of the first circle with wrt to the center of second circles. Then extend this vector to the length of c1c2+r1.(c1c2 is the distance between centres). The would give the relative position of answer wrt centre of the second circle. Then you can find the absolute position of the answer.

Solution link

1 Like

My Code is running correctly on my local machine as well as other IDE’s on sample test cases, but not on CodeChef.
Error is that my Code gives Wrong Answer
I can’t figure out what’s wrong with my code. I have tried to follow the approach mentioned in the Editorial.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	
	int test_cases; cin>>test_cases;
	
	for (int i = 0; i < test_cases; ++i)
	{
		long int X1, Y1, R1, X2, Y2, R2;
		cin>>X1>>Y1>>R1>>X2>>Y2>>R2;


		if(X1==X2 && Y1==Y2)
		{
			if(R1>R2)
			{	printf("YES\n");
				printf("%f %f\n",double(X1+R1),double(Y1)); }
			else
				printf("NO\n");
		}
		else
		{
                  //distance between centres of circles
			double dis1=(X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2);
			dis1=sqrt(dis1);
                      
                  //finding the point farthest from circle 2 centre on circle 1
			double y=Y1 - R1*(double(Y2-Y1)/dis1);
			double x=X1 - R1*(double(X2-X1)/dis1);

                    //distance between the point found and circle2 center

			double dis=(x-X2)*(x-X2) + (y-Y2)*(y-Y2);

			if(dis>R2*R2)
			{	printf("YES\n");
				printf("%f %f\n",double(x),double(y)); 	}
			else
				printf("NO\n");
		}
	}
}

My solution passed successfully and I don’t think it should have passed.
My approach is pretty straightforward.
In my approach if two circles are intersecting, I just answered one of the intersection points of the two circles. Now, the intersection point is on the perimeter of first circle which satisfies one of the conditions but does not satisfy the second condition as it does not lie strictly outside the second circle. Were the test cases weak or am I missing something?

Link to my solution : https://www.codechef.com/viewsolution/26008193

2 Likes

Maybe you got around due to that 10^-6 error margin.

Hello everyone,
I have used the logic that if a circle has its center coordinates as integers and also the radius as the integer,then there must be atleast 4 points who have their coordinates as an integer.
Now,two circles can have
1)No intersection-Hence the answer is yes and the point can be any one of them.
2)One point intersection-The answer is yes and the point will be anyone of those 4 points the one that doesn’t lie on the second circle.
3)Two point intersection-The answer is yes again and the point is the one which doesn’t lie on the second circle
4)circle coincide-No point
Please help me with my solution.
Link to solution-(https://www.codechef.com/viewsolution/26023571)

1 Like

In case of no intersection, first circle could lie inside second one. In that case answer is NO.
Your approach will fail in that case as you are answering YES

1 Like