# CIRCLES2 - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Rami

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

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.

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

// 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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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

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

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.

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âŚ

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â ; )

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.

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

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);
}
}

}
``````

}

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.

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