2CUnreviewed2600GPT-5.4 (high)

Commentator problem

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

geometry

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

For a circle of radius $r$ , seen from a point at distance $d$ 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 $\frac{r_i}{d_i}$ are equal too. So you are really looking for a point $P$ such that

\frac{|PC_1|}{r_1}=\frac{|PC_2|}{r_2}=\frac{|PC_3|}{r_3}.

Maximizing the common angle means minimizing that common ratio’s reciprocal.

For two circles, the locus of points with

\frac{|PC_i|}{|PC_j|}=\frac{r_i}{r_j}

is an Apollonius circle, or a line if $r_i=r_j$ . So there are at most two candidates overall. That’s the geometry picture; now do the algebra without making it miserable.

Let $P=(x,y)$ and let $k$ be the common squared ratio:

(x-x_i)^2+(y-y_i)^2 = k r_i^2.

Subtract the first equation from the other two. The $x^2+y^2$ terms die, and you get a $2\times2$ linear system in $(x,y)$ whose right-hand side depends linearly on $k$ .

Solve that linear system to write

P = P_0 + kV.

Then substitute into one original equation:

|P_0 + kV - C_1|^2 = k r_1^2,

which is a quadratic in $k$ . Each real root gives one candidate point. Recover the point, discard anything numerically invalid / inside a stadium, and choose the candidate with the smallest $k$ because

\alpha = 2\arcsin\!\left(\frac{1}{\sqrt{k}}\right)

is larger when $k$ is smaller.

Observation 1: the trigonometry collapses to a ratio

Let stadium $i$ have center $C_i=(x_i,y_i)$ and radius $r_i$ . If the commentator stands at point $P$ , and $d_i=|PC_i|$ , then the stadium is seen under the angle between the two tangents from $P$ to the circle.

From the standard right-triangle picture,

\sin\left(\frac{\alpha_i}{2}\right)=\frac{r_i}{d_i},

\alpha_i = 2\arcsin\left(\frac{r_i}{d_i}\right).

Therefore, the condition that all three stadiums are seen under the same angle is exactly

\frac{r_1}{d_1}=\frac{r_2}{d_2}=\frac{r_3}{d_3}.

Equivalently,

\frac{d_1}{r_1}=\frac{d_2}{r_2}=\frac{d_3}{r_3}=\lambda.

And because

\alpha = 2\arcsin\left(\frac{1}{\lambda}\right),

maximizing the common viewing angle is the same as minimizing $\lambda$ .

So the whole problem is now:

Find a point $P$ 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.

Observation 2: Apollonius circles are the geometry, but algebra is cleaner

For a fixed pair $(i,j)$ , the locus

\frac{|PC_i|}{|PC_j|}=\frac{r_i}{r_j}

is an Apollonius circle, or a line if $r_i=r_j$ .

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.

Turning it into equations

Let

k = \lambda^2.

Then the condition $d_i = \lambda r_i$ becomes

(x-x_i)^2+(y-y_i)^2 = k r_i^2 \qquad (i=1,2,3),

where $P=(x,y)$ .

Now subtract the first equation from the second and third. The annoying $x^2+y^2$ terms vanish:

2(x_2-x_1)x + 2(y_2-y_1)y = (x_2^2+y_2^2-x_1^2-y_1^2) + k(r_1^2-r_2^2),

2(x_3-x_1)x + 2(y_3-y_1)y = (x_3^2+y_3^2-x_1^2-y_1^2) + k(r_1^2-r_3^2).

This is a $2\times2$ linear system in $(x,y)$ , and its determinant is

4\big((x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)\big).

Because the centers are not collinear, this determinant is nonzero. So $(x,y)$ is an affine function of $k$ :

P = P_0 + kV.

That is the key simplification.

One quadratic, done

Now substitute $P=P_0+kV$ back into any original equation, say the first one:

|P_0 + kV - C_1|^2 = k r_1^2.

Expand it:

(V\cdot V)k^2 + \big(2V\cdot(P_0-C_1)-r_1^2\big)k + |P_0-C_1|^2 = 0.

Boom: a quadratic in $k$ .

No real roots: no answer.
One real root: one candidate.
Two real roots: two candidates.

For each real root $k$ , recover the corresponding point $P$ from the linear system.

Among all valid candidates, choose the one with the smallest $k$ , because

\alpha = 2\arcsin\left(\frac{1}{\sqrt{k}}\right)

is strictly decreasing in $k$ .

Why validity checks are still a good idea

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

\frac{|PC_1|}{r_1},\ \frac{|PC_2|}{r_2},\ \frac{|PC_3|}{r_3}

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.

Special case sanity check

If all radii are equal, then the right-hand sides above do not depend on $k$ , so $P$ is fixed immediately: it is just the circumcenter of the three centers. Then $k$ is obtained from one linear equation. Nice sanity check, and exactly what the sample does.

Complexity

Everything is a constant amount of arithmetic:

O(1)

time and

O(1)

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;
}

View on Codeforces Back to the list