Another could be taking up a calculas based approach. Take the parametric equation of the two circles, get distance equation of the two circles and differentiate the equation to get the minimum and maximum distance between the two circles and hence include all values of k between min and max distance. This way different positions of circles won’t have to be considered as different cases. I haven’t personally coded this solution, but this should work theoretically.
Since all the solutions seem to be taking sqrt for calculating the distance between the centers. Why we don’t have double precision issues here? Can we solve this problem without any double calculation?
1 Like
After finding minimum and maximum pair for each circle pair, i used two technique to answer the query:
- declare a array d[1000001]={0}, and for each pair, increment the value of d[i], i ∈ (minimum(i’th pair),maximum(i’th pair)).
- Another way is store each min,max pair in vector of pair. Then sort according to minimum distance and apply linear search for each query.
But i get tle in both case, how can i do query part more efficiently?
abhijeet_kr refer to this problem of Array Manipulation in Hackerrank…Array Manip. It will help you in understanding your doubt.
Why this code is giving tle??? I don’t understand. My approach is same as the explanation. Please tell.
import java.util.*;
class Solution {
static final Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int n = sc.nextInt();
int q = sc.nextInt();
int max = 1000000;
int ar[] = new int[max];
int qq[] = new int[q];
double arr[][] = new double[n][3];
int tot = n*(n-1)/2;
double ds[][] = new double[tot][2];
for(int i=0 ; i<n; i++){
arr[i][0] = sc.nextDouble();
arr[i][1] = sc.nextDouble();
arr[i][2] = sc.nextDouble();
}
for(int i = 0; i<q ; i++){
qq[i] = sc.nextInt();
}
int in = 0;
for(int i = 0; i< n-1; i++){
for(int j = i+1; j<n;j++){
double x = Math.pow(( Math.pow( (arr[i][0]-arr[j][0]), 2) + Math.pow( (arr[i][1]-arr[j][1]), 2)), 0.5);
if(x >= arr[i][2]+arr[j][2]){
ds[in][0] = x - arr[i][2] - arr[j][2];
ds[in][1] = x + arr[i][2] + arr[j][2];
ar[ds[in][0]>(int)ds[in][0]?(int)ds[in][0]+1:(int)ds[in][0]] += 1;
if((int)ds[in][0] < max-1)
ar[(int)ds[in][1]+1] = ar[(int)ds[in][1]+1] - 1;
in++;
}
else if((x + arr[i][2]<arr[j][2]?arr[i][2]:arr[j][2]) <= (arr[i][2]>arr[j][2]?arr[i][2]:arr[j][2]) ){
ds[in][0] = (arr[i][2]>arr[j][2]?arr[i][2]:arr[j][2]) - x - (arr[i][2]<arr[j][2]?arr[i][2]:arr[j][2]);
ds[in][1] = 2*(arr[i][2]>arr[j][2]?arr[i][2]:arr[j][2]) - ds[in][0];
if(ds[in][0]<0){
ds[in][0] = 0;
ds[in][1] = x+arr[i][2]+arr[j][2];
}
ar[ds[in][0]>(int)ds[in][0]?(int)ds[in][0]+1:(int)ds[in][0]] += 1;
if((int)ds[in][0] < max-1)
ar[(int)ds[in][1]+1] = ar[(int)ds[in][1]+1] - 1;
in++;
}
}
}
for(int i = 1 ; i < max; i++){
ar[i] += ar[i-1];
}
for(int ii = 0; ii < q ; ii++){
if(qq[ii]<max){
System.out.println(ar[qq[ii]]);
}else
System.out.println("0");
}
}
}
i didn’t understood the last part of …answer[minima]++, answer[maxima+1]–…blah, How can we answer the queries ? its quiet abstract please explain…
Because you just need very less precision to get AC as you are just concerned about the floor and ceil value of the distance… nothing else… As the inputs are integer… My solution don’t contain double data type anywhere…(obviously I am calculating sqrt once) So solution seems to be comparatively more faster when we don’t use double.
It was only a basic circle geometry… nothing else…
Use a smart way to update each of values from min to max…
i.e. one of the technique could be…
d[min]++;
d[max+1]–;
For each pair of circle…
Then do
d[i]+=d[i-1]
For each index in d…
This will create the similar array which you created with very less time complexity and it won’t go for TLE…
Did you try using fast input too ? Scanners and System.out.println can be quite slow.
Thanks @l_returns4, its working.
I think you should write a blog on such tricks, this help many beginner. 
1 Like
Okay I ll try… U r welcome 
Avoid using double data type more… it’s not needed as per my solution… I ll upload authors solution today… Have a look… Avoiding using double will make your code fast… Mine runs in 0.06 in c++
I have integers everywhere…
You can have a look at my solution by using above link in the editorial…
I have uploaded my solution… (Author’s code link)
Use a smart way to update each of values from min to max…
i.e. one of the technique could be…
d[min]++;
d[max+1]–;
For each pair of circle…
Then do
d[i]+=d[i-1]
For each index in d…
This technique will excecute following code indirectly…
For i=min to max
d[i]++;