BEACIRC - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: pawnage

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Geometry, Math

PROBLEM:

Given N circles, find how many unordered triplets of circles have the following property: one circle passes through the two intersection points and the centers of the two other circles.

QUICK EXPLANATION:

Let (C_{1}, C_{2}, C_{3}) be a triplet that is beautiful. Let C_{3} pass through centers of C_{1} and C_{2} and through their intersections.

The Center of C_{3} will be the midpoint of line segment formed by the center of C_{1} and the center of C_{2}.

But this doesn’t guarantee that it passes through intersections of C_{1} and C_{2}. For that, we need to find one more condition.

Observe that centers of C_{1} and C_{3} and one of their intersection points will form a right triangle if a circle passes through these points. So,

R_{1}^{2} + R_{2}^{2} = distance(Center C_{1}, Center C_{2})

Using these two conditions we can find the required answer.

EXPLANATION:

Let I_{1} and I_{2} be the two intersection points of C_{1} and C_{2}.
Let O_{1}, O_{2} and O_{3} be the centers of C_{1}, C_{2}, C_{3} respectively.
Let R_{1}, R_{2} and R3 be the centers of C_{1}, C_{2}, C_{3} respectively.
Let C_{3} pass through all the mentioned four points.

Observe triangles O_{1} I_{1} O_{2} and O_{1}I_{2}O_{2}. These two triangles are congruent as O_{1}I_{1} = O_{1}I_{2} = R_{1} and O_{2}I_{1} = O_{2}I_{2} = R_{2}.
Hence, \angle O_{1} I_{1} O_{2} = \angle O_{1} I_{2} O_{2} .

Now observe that O_{1} I_{1} O_{2}I_{2} is a cyclic quadrilateral in circle C_{3}. In a cyclic quadrilateral sum of opposite angles is 180\degree.

Hence, \angle O_{1} I_{1} O_{2} + \angle O_{1} I_{2} O_{2} = 180\degree.
So, \angle O_{1} I_{1} O_{2} = \angle O_{1} I_{2} O_{2} = 90\degree.
If a chord subtends 90\degree angle on the circle, then it is a diameter.
Therefore, O_{1} O_{2} is the diameter of C3.

Hence, O_{3} = \frac{O_{1} + O_{2}}{2} and R_{3} = \frac{distance(O_{1}, O_{2})}{2}.

Note that only this condition does not guarantee a solution, as the circle might not pass through the intersections.

We see that, since \triangle O_{1} I_{1} O_{2} is right-angled, we have, R_{1}^{2} + R_{2}^{2} = distance(O_{1}, O_{2})^{2} = 4*R_{3}^{2}.

So, we can store the frequency of each circle in a map. Iterate over every pair of circles and based on the two conditions above find O_{3} and R_{3}.

ALTERNATE EXPLANATION:

Alternatively, for each pair of circles, we can find O_{3} and R_{3} based on the first condition of the previous solution. Now, check if the O_{3} is at a distance R_{3} from both the intersection points which can found like this.
But this solution will be lengthy and time-consuming.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;

ll distance(vector<ll> &a, vector<ll> &b) {
    ll dist = (a[0] - b[0])*(a[0] - b[0]) + (a[1] - b[1])*(a[1] - b[1]);
    ll dia = (int)sqrt(dist);
    return dia*dia == dist ? dia : -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t; cin>>t;
    while(t--) {
        int n, ans = 0; cin>>n;
        vector<vector<ll>> inp(n, vector<ll>(3));
        map<vector<ll>, int> mp;

        for(int i=0; i<n; i++) {
            cin>>inp[i][0]>>inp[i][1]>>inp[i][2];
            mp[inp[i]]++;
        }

        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                ll x1 = inp[i][0], x2 = inp[j][0];
                ll y1 = inp[i][1], y2 = inp[j][1];
                ll dist = distance(inp[i], inp[j]);

                if((x1+x2)%2 == 0 && (y1+y2)%2 == 0 && dist != -1 && dist%2 == 0 && dist*dist == inp[i][2]*inp[i][2] + inp[j][2]*inp[j][2]) {
                    vector<ll> tmp(3);
                    tmp[0] = (x1+x2) / 2;
                    tmp[1] = (y1+y2) / 2;
                    tmp[2] = dist / 2;
                    
                    if(mp.find(tmp) != mp.end()) {
                        ans += mp[tmp];
                    }
                }
            }
        }

        cout<<ans<<endl;
    }

    return 0;
}
Another Solution
#include <bits/stdc++.h>
#define F first
#define S second
#define EPS 0.01
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;

vector<double> get_line(double x1,double x2, double y1,double y2,double r1, double r2) {
    x2 = x2-x1;
    y2 = y2-y1;
    double A = -2 * x2;
    double B = -2 * y2;
    double C = x2*x2 + y2*y2 + r1*r1 - r2*r2;
    vector<double> line = vector<double>(3);
    line[0] = A;
    line[1] = B;
    line[2] = C;
    return line;
}

vector<double> intersection(vector<double> line, double r){
    double a, b, c; 
    a = line[0];
    b = line[1];
    c = line[2];
    double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);

    if (c*c > r*r*(a*a+b*b)+EPS)
        return vector<double>(0);
    else if (abs (c*c - r*r*(a*a+b*b)) < EPS)
        return vector<double>(0);
    else {
        double d = r*r - c*c/(a*a+b*b);
        double mult = sqrt (d / (a*a+b*b));
        double ax, ay, bx, by;
        ax = x0 + b * mult;
        bx = x0 - b * mult;
        ay = y0 - a * mult;
        by = y0 + a * mult;
        return vector<double>({ax,ay,bx,by});
    }
    return vector<double>(0);
}

int required_radius(long long x1,long long  x2, long long y1,long long y2) {
    long long dist = (x2-x1)*(x2-x1) + (y2-y1) * (y2-y1);
    long long tmp = sqrt(dist);
    if(tmp*tmp == dist && tmp%2 ==0)
        return tmp/2;
    if((tmp+1)*(tmp+1)== dist && (tmp+1)%2 == 0)
        return (tmp+1)/2;
    return -1;
}

ii get_center(int x1,int x2, int y1, int y2) {
    if((x1+x2)%2 ==0 and (y1+y2)%2 == 0) {
        return {(x1+x2)/2,(y1+y2)/2};
    }
    return {-1,-1};
}

double s2(double a) {
    return a*a;
}

int verify_points(vector<double> inters, ii center, double x1, double y1, double r_sq) {
    double dist = s2(inters[0]-center.first+x1)+s2(inters[1]-center.second+y1);
    if (abs(dist-r_sq) < EPS) {
        return 1;
    }
    return 0;
}

iii get_req_circle(int x1,int x2, int y1,int y2,int r1, int r2) {
    if(x1==x2 && y1==y2) {
        return {{-1,-1},-1};
    }
    ii center = get_center(x1,x2,y1,y2);

    if(center.first == -1) return {{-1,-1},-1};

    long long radius = required_radius(x1,x2,y1,y2);

    if(radius == -1) return {{-1,-1},-1};

    vector<double> line = get_line(x1,x2,y1,y2,r1,r2);
    vector<double> inst = intersection(line,r1);

    if(inst.size()==0) return {{-1,-1},-1};

    if(verify_points(inst,center,x1,y1,radius*radius)) {
        return {center,radius};
    }
    return {{-1,-1},-1};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;cin>>t;
    while(t--) {
        int n;cin>>n;
        vector<iii> a(n);
        map<iii,int> mp;
        for(int i=0;i<n;i++) {
            cin>>a[i].first.first >> a[i].first.second >> a[i].second;
            mp[a[i]]++;
        }
        int ans = 0;
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                iii rt = get_req_circle(a[i].F.F,a[j].F.F,a[i].F.S,a[j].F.S,a[i].S,a[j].S);
                ans += mp[rt];
            }
        }
        cout<<ans<<"\n";
    }
}
3 Likes

https://www.codechef.com/viewsolution/36683527

I tried pretty much the same thing. Can you see why the answer is coming out to be wrong? Is it something to do with the sqrt function?

I am not sure, but it seems your code gives wrong answer on this
0 0 12
0 13 5
0 6 6

(R1)^2+(R2)^2=4*R3^2. ??

Diameter = 2*radius

in. the editorial it is given :sq(r1)+sq(r1)

@lazarus123 It is a typo, it should be sq(r1) + sq(r2). @pawnage Please correct this.

1 Like

fixed