Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
For a circle of radius , seen from a point at distance from its center, what is the angle between the two tangents? Try expressing the half-angle in a right triangle.
If the three viewing angles are equal, then the values of are equal too. So you are really looking for a point such that
Maximizing the common angle means minimizing that common ratio’s reciprocal.
For two circles, the locus of points with
is an Apollonius circle, or a line if . So there are at most two candidates overall. That’s the geometry picture; now do the algebra without making it miserable.
Let and let be the common squared ratio:
Subtract the first equation from the other two. The terms die, and you get a linear system in whose right-hand side depends linearly on .
Solve that linear system to write
Then substitute into one original equation:
which is a quadratic in . Each real root gives one candidate point. Recover the point, discard anything numerically invalid / inside a stadium, and choose the candidate with the smallest because
is larger when is smaller.
Let stadium have center and radius . If the commentator stands at point , and , then the stadium is seen under the angle between the two tangents from to the circle.
From the standard right-triangle picture,
so
Therefore, the condition that all three stadiums are seen under the same angle is exactly
Equivalently,
And because
maximizing the common viewing angle is the same as minimizing .
So the whole problem is now:
Find a point such that its distances to the three centers are proportional to the three radii, and among all such points choose the one with the smallest proportionality constant.
That’s a weighted circumcenter problem. Ordinary circumcenter is just the equal-radii version wearing a fake moustache.
For a fixed pair , the locus
is an Apollonius circle, or a line if .
So geometrically, we are intersecting two such loci, hence there are at most two candidates.
You can go full circle-circle intersection mode here, but that’s a great way to turn a clean problem into geometry spaghetti. A much nicer route is to keep one extra parameter.
Let
Then the condition becomes
where .
Now subtract the first equation from the second and third. The annoying terms vanish:
This is a linear system in , and its determinant is
Because the centers are not collinear, this determinant is nonzero. So is an affine function of :
That is the key simplification.
Now substitute back into any original equation, say the first one:
Expand it:
Boom: a quadratic in .
For each real root , recover the corresponding point from the linear system.
Among all valid candidates, choose the one with the smallest , because
is strictly decreasing in .
Mathematically, any real solution of the system gives equal ratios. But numerically, floating-point dust exists because the universe hates us.
So after computing a candidate point, it is wise to verify that
are equal up to a tiny epsilon, and also that the point is not inside a stadium.
Those checks are cheap and make the solution robust.
If all radii are equal, then the right-hand sides above do not depend on , so is fixed immediately: it is just the circumcenter of the three centers. Then is obtained from one linear equation. Nice sanity check, and exactly what the sample does.
Everything is a constant amount of arithmetic:
time and
memory.
This is one of those problems where the code is short, and the hard part is noticing which equation to smack until the ugly terms fall out.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Circle {
long double x, y, r;
};
struct Point {
long double x, y;
};
Point getPoint(long double t,
long double A1, long double B1, long double C1, long double D1,
long double A2, long double B2, long double C2, long double D2,
long double det) {
long double rhs1 = C1 + D1 * t;
long double rhs2 = C2 + D2 * t;
return {
(rhs1 * B2 - rhs2 * B1) / det,
(A1 * rhs2 - A2 * rhs1) / det
};
}
bool valid(const vector<Circle>& c, const Point& p) {
vector<long double> ratio;
for (int i = 0; i < 3; ++i) {
long double dx = p.x - c[i].x;
long double dy = p.y - c[i].y;
long double d = sqrtl(max(0.0L, dx * dx + dy * dy));
if (d + 1e-9L < c[i].r) return false;
ratio.push_back(d / c[i].r);
}
long double mn = *min_element(ratio.begin(), ratio.end());
long double mx = *max_element(ratio.begin(), ratio.end());
long double scale = max(1.0L, fabsl(mx));
return mx - mn <= 1e-8L * scale;
}
int main() { setIO();
vector<Circle> c(3);
for (int i = 0; i < 3; ++i) cin >> c[i].x >> c[i].y >> c[i].r;
long double x1 = c[0].x, y1 = c[0].y, r1 = c[0].r;
long double x2 = c[1].x, y2 = c[1].y, r2 = c[1].r;
long double x3 = c[2].x, y3 = c[2].y, r3 = c[2].r;
long double A1 = 2.0L * (x2 - x1);
long double B1 = 2.0L * (y2 - y1);
long double C1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
long double D1 = r1 * r1 - r2 * r2;
long double A2 = 2.0L * (x3 - x1);
long double B2 = 2.0L * (y3 - y1);
long double C2 = x3 * x3 + y3 * y3 - x1 * x1 - y1 * y1;
long double D2 = r1 * r1 - r3 * r3;
long double det = A1 * B2 - A2 * B1;
if (fabsl(det) < 1e-18L) return 0;
long double px = (C1 * B2 - C2 * B1) / det;
long double qx = (D1 * B2 - D2 * B1) / det;
long double py = (A1 * C2 - A2 * C1) / det;
long double qy = (A1 * D2 - A2 * D1) / det;
long double dx = px - x1;
long double dy = py - y1;
long double a = qx * qx + qy * qy;
long double b = 2.0L * (qx * dx + qy * dy) - r1 * r1;
long double cc = dx * dx + dy * dy;
vector<long double> roots;
if (fabsl(a) < 1e-18L) {
if (fabsl(b) < 1e-18L) return 0;
roots.push_back(-cc / b);
} else {
long double disc = b * b - 4.0L * a * cc;
long double scale = max({1.0L, fabsl(b * b), fabsl(4.0L * a * cc)});
if (disc < -1e-18L * scale) return 0;
if (disc < 0) disc = 0;
long double sq = sqrtl(disc);
long double t1 = (-b - sq) / (2.0L * a);
long double t2 = (-b + sq) / (2.0L * a);
roots.push_back(t1);
if (fabsl(t1 - t2) > 1e-12L * max({1.0L, fabsl(t1), fabsl(t2)})) {
roots.push_back(t2);
}
}
bool found = false;
long double bestT = 0;
Point ans{};
for (long double t : roots) {
if (!(t > 0)) continue;
Point p = getPoint(t, A1, B1, C1, D1, A2, B2, C2, D2, det);
if (!valid(c, p)) continue;
if (!found || t < bestT) {
found = true;
bestT = t;
ans = p;
}
}
if (!found) return 0;
if (fabsl(ans.x) < 5e-6L) ans.x = 0;
if (fabsl(ans.y) < 5e-6L) ans.y = 0;
cout << fixed << setprecision(5) << ans.x << ' ' << ans.y;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Circle {
long double x, y, r;
};
struct Point {
long double x, y;
};
Point getPoint(long double t,
long double A1, long double B1, long double C1, long double D1,
long double A2, long double B2, long double C2, long double D2,
long double det) {
long double rhs1 = C1 + D1 * t;
long double rhs2 = C2 + D2 * t;
return {
(rhs1 * B2 - rhs2 * B1) / det,
(A1 * rhs2 - A2 * rhs1) / det
};
}
bool valid(const vector<Circle>& c, const Point& p) {
vector<long double> ratio;
for (int i = 0; i < 3; ++i) {
long double dx = p.x - c[i].x;
long double dy = p.y - c[i].y;
long double d = sqrtl(max(0.0L, dx * dx + dy * dy));
if (d + 1e-9L < c[i].r) return false;
ratio.push_back(d / c[i].r);
}
long double mn = *min_element(ratio.begin(), ratio.end());
long double mx = *max_element(ratio.begin(), ratio.end());
long double scale = max(1.0L, fabsl(mx));
return mx - mn <= 1e-8L * scale;
}
int main() { setIO();
vector<Circle> c(3);
for (int i = 0; i < 3; ++i) cin >> c[i].x >> c[i].y >> c[i].r;
long double x1 = c[0].x, y1 = c[0].y, r1 = c[0].r;
long double x2 = c[1].x, y2 = c[1].y, r2 = c[1].r;
long double x3 = c[2].x, y3 = c[2].y, r3 = c[2].r;
long double A1 = 2.0L * (x2 - x1);
long double B1 = 2.0L * (y2 - y1);
long double C1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
long double D1 = r1 * r1 - r2 * r2;
long double A2 = 2.0L * (x3 - x1);
long double B2 = 2.0L * (y3 - y1);
long double C2 = x3 * x3 + y3 * y3 - x1 * x1 - y1 * y1;
long double D2 = r1 * r1 - r3 * r3;
long double det = A1 * B2 - A2 * B1;
if (fabsl(det) < 1e-18L) return 0;
long double px = (C1 * B2 - C2 * B1) / det;
long double qx = (D1 * B2 - D2 * B1) / det;
long double py = (A1 * C2 - A2 * C1) / det;
long double qy = (A1 * D2 - A2 * D1) / det;
long double dx = px - x1;
long double dy = py - y1;
long double a = qx * qx + qy * qy;
long double b = 2.0L * (qx * dx + qy * dy) - r1 * r1;
long double cc = dx * dx + dy * dy;
vector<long double> roots;
if (fabsl(a) < 1e-18L) {
if (fabsl(b) < 1e-18L) return 0;
roots.push_back(-cc / b);
} else {
long double disc = b * b - 4.0L * a * cc;
long double scale = max({1.0L, fabsl(b * b), fabsl(4.0L * a * cc)});
if (disc < -1e-18L * scale) return 0;
if (disc < 0) disc = 0;
long double sq = sqrtl(disc);
long double t1 = (-b - sq) / (2.0L * a);
long double t2 = (-b + sq) / (2.0L * a);
roots.push_back(t1);
if (fabsl(t1 - t2) > 1e-12L * max({1.0L, fabsl(t1), fabsl(t2)})) {
roots.push_back(t2);
}
}
bool found = false;
long double bestT = 0;
Point ans{};
for (long double t : roots) {
if (!(t > 0)) continue;
Point p = getPoint(t, A1, B1, C1, D1, A2, B2, C2, D2, det);
if (!valid(c, p)) continue;
if (!found || t < bestT) {
found = true;
bestT = t;
ans = p;
}
}
if (!found) return 0;
if (fabsl(ans.x) < 5e-6L) ans.x = 0;
if (fabsl(ans.y) < 5e-6L) ans.y = 0;
cout << fixed << setprecision(5) << ans.x << ' ' << ans.y;
}