Beautiful Circles Unintended Solution

editorial
1

Here is the link to the problem:
https://www.codechef.com/DEM2020/problems/BEACIRC
Here is the link to my submission:
https://www.codechef.com/viewsolution/36693440

I thought of the problem for a complete 1 hour and could not come up with a solution. After that, I looked at the given sample test case and came up with a solution based on pure guesswork. Here is my approach:

Consider every pair of circles and try to find the 3rd circle which would match with the 2 circles following the properties given. Considering the first 2 circles as (x1,y1,r1) and (x2,y2,r2):

Find out two values value1 = (r1^2 + r2^2), value2 = (x1-x2)^2 + (y1-y2)^2
Here values1 is the sum of squares of the radii of the two circles and value2 is the square of the distance between the centers of the two circles.
If the 2 values are different there is no possible solution. If they are the same, then the radius of the third circle can be found out by the formula sqrt(value1/4). If this value is not an integer then again no possible solution. Otherwise, the final circle will have the following center and radius: ((x1+x2)/2, (y1+y2)/2, sqrt(value1/4)).

Now, finding the number of occurrences of such circles can be easily done by a map.
So, the total time complexity will be O(N^2Log(N)).

I don’t think this is the intended solution so thought I should share it. PS: I have no way to prove this is correct until now.

2

I was not able to solve the problem so thank you.
the link to your solution is wrong please update it I would really like to see it.

3

Done, thanks for telling me

1 Like
4

How about this ?

  1. Select two circles Ci & Cj where i != j .
  2. Check if distance between their centres < sum of their radii.
  3. If 2 is true, only then will they intersect at two distinct points. Now see if their is a circle having Centre at mid points of the line joining centres of Ci and Cj. Also check if radius of this new circle is equal to half of distance between Ci and Cj.
  4. Add all such occurences of this third circle (as we may have multiple such circles) in the result.
    IDK why but it gave WA !
1 Like
5

This is indeed correct solution.
Proof - Let the center of circles be c1, c2 and points of intersection be d1, d2.
Now, since the third circle should pass through all four points implies points c1, c2, d1, d2 forms a cyclic quadrilateral.
Now, using property- Sum of opposite angles of a cyclic quadrilateral is π, you can easily deduce that angle(c1,d1,c2) = angle(c1,d2,c2) = π/2.

6

@nprakhar Can you please help me in this problem Link

7

Yeah I just figured that out. Thanks for explaining it in a clearer way.

8

My AC code ,its quite neat just in case somebody wants to refer

AC_CODE 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ar array 
#define pb push_back 
#define vi vector
#define FOR(i,j,n) for(int i=j;i<n;i++)
#define all(a) a.begin(),a.end()
int d(ar<int,3> a,ar<int,3>b){
  return (a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]);
}
bool ok(ar<int,3>a,ar<int,3>b){
  return d(a,b)==a[2]*a[2]+b[2]*b[2] ;
}
void solve(){ 
  int n ;cin >> n ;
  vi<ar<int,3>>a(n) ;
  FOR(i,0,n)
    FOR(j,0,3)
      cin >> a[i][j],a[i][j]*=2;
  map<ar<int,3>,int >mp ;
  for(ar<int,3> x:a)
    mp[x]++ ;
  set<ar<int,3>>s(all(a));a.clear() ;
  for(ar<int,3> x:s)
    a.pb(x);
  n= a.size();int ans =0;
  FOR(i,0,n){
    FOR(j,i+1,n){
      int di=d(a[i],a[j]),cd=sqrt(d(a[i],a[j]));
      if(!ok(a[i],a[j])||di^(cd*cd))
        continue ;
      ar<int,3>ck ={(a[i][0]+a[j][0])/2,(a[i][1]+a[j][1])/2,cd/2};
      ans+=mp[a[i]]*mp[a[j]]*mp[ck] ;
    }
  }
  cout << ans << "\n" ;
}
signed main() {
  int t ;cin >> t ;
  while(t--)
    solve() ;
}
9

@cubefreak777 I have done the same as you.
Can you please help me Link to submission

10

Our approaches look almost same ,you can try checking my solution to find what you missed ,one suggestion just multiply everything with 2 so that you dont have to check for the parity everytime

11

It is the intended solution (I am one of the problemsetters of the contest) - although using an unordered_map, you can do it in O(N^2) as well.

It is easily derived from cyclic quadrilateral property, or from the cosine law in trigonometry.