PROBLEM LINK:
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";
}
}