#1195410 (C++23) No.172 UFOを捕まえろ

• 問題: No.172 UFOを捕まえろ
• ユーザー: T1610
• 提出日時: 2026-10-26 00:38:39
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 5,000 ms
• コード長: 5,999 bytes
• コンパイル時間: 4,117 ms
• コンパイル使用メモリ: 382,800 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-26 00:38:54
• 合計ジャッジ時間: 5,911 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 21

ソースコード

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (ll i = (s); i < (ll)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (ll i = (ll)(s - 1); i >= (ll)(e); i--)
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T, typename U>
T chmax(T& a, const U& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <typename T, typename U>
T chmin(T& a, const U& b) {
    if (a <= b) return false;
    a = b;
    return true;
}

void yes_no(bool f, string yes = "Yes", string no = "No") { cout << (f ? yes : no) << "\n"; }

//----------基本部分-----------------------------------------------------------------------
#define X real()
#define Y imag()
#define x(p) real(p)
#define y(p) imag(p)
#define curr(P, i) P[i]
#define next(P, i) P[(i + 1) % P.size()]
#define prev(P, i) P[(i + P.size() - 1) % P.size()]

typedef long double D;

const D EPS = 1e-8;
const D INF = 1e12;
const D PI = acos(-1);
typedef complex<D> P;
typedef complex<D> point;
namespace std {
bool operator<(const P& a, const P& b) {
    return x(a) != x(b) ? x(a) < x(b) : y(a) < y(b);
}
} // namespace std
D cross(const P& a, const P& b) {
    return y(conj(a) * b);
}
D dot(const P& a, const P& b) {
    return x(conj(a) * b);
}

struct L : public vector<P> {
    L(const P& a, const P& b) {
        push_back(a);
        push_back(b);
    }
};

typedef vector<P> G;
typedef vector<P> polygon;

struct C {
    P p;
    D r;
    C(const P& p, D r) : p(p), r(r) {}
};
// 点の進行方向
int ccw(P a, P b, P c) {
    b -= a;
    c -= a;
    if (cross(b, c) > 0) return +1;   // counter clockwise
    if (cross(b, c) < 0) return -1;   // clockwise
    if (dot(b, c) < 0) return +2;     // c--a--b on line
    if (norm(b) < norm(c)) return -2; // a--b--c on line
    return 0;
}
//------------------------------------------------------------------------------------------
//---------交差判定・距離等-------------------------------------------------------------------
bool intersectLL(const L& l, const L& m) {
    return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // non-parallel
           abs(cross(l[1] - l[0], m[0] - l[0])) < EPS;   // same line
}
bool intersectLS(const L& l, const L& s) {
    return cross(l[1] - l[0], s[0] - l[0]) * // s[0] is left of l
               cross(l[1] - l[0], s[1] - l[0]) <
           EPS; // s[1] is right of l
}
bool intersectLP(const L& l, const P& p) {
    return abs(cross(l[1] - p, l[0] - p)) < EPS;
}
bool intersectSS(const L& s, const L& t) {
    return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
           ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}
bool intersectSP(const L& s, const P& p) {
    return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; // triangle inequality
}
P projection(const L& l, const P& p) {
    D t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
    return l[0] + t * (l[0] - l[1]);
}
P reflection(const L& l, const P& p) {
    return p + (D)2.0 * (projection(l, p) - p);
}
D distanceLP(const L& l, const P& p) {
    return abs(p - projection(l, p));
}
D distanceLL(const L& l, const L& m) {
    return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);
}
D distanceLS(const L& l, const L& s) {
    if (intersectLS(l, s)) return 0;
    return min(distanceLP(l, s[0]), distanceLP(l, s[1]));
}
D distanceSP(const L& s, const P& p) {
    const P r = projection(s, p);
    if (intersectSP(s, r)) return abs(r - p);
    return min(abs(s[0] - p), abs(s[1] - p));
}
D distanceSS(const L& s, const L& t) {
    if (intersectSS(s, t)) return 0;
    return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
               min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
P crosspoint(const L& l, const L& m) {
    D A = cross(l[1] - l[0], m[1] - m[0]);
    D B = cross(l[1] - l[0], l[1] - m[0]);
    if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
    if (abs(A) < EPS) assert(false);               // !!!PRECONDITION NOT SATISFIED!!!
    return m[0] + B / A * (m[1] - m[0]);
}
//--------------------------------------------------------------------------------------
// 点が多角形内にあるか判定(polygonは反時計回り)               CGL_3_C
enum { OUT,
       ON,
       IN };
int contains(const polygon& P, const point& p) {
    bool in = false;
    for (int i = 0; i < P.size(); ++i) {
        point a = curr(P, i) - p, b = next(P, i) - p;
        if (y(a) > y(b)) swap(a, b);
        if (y(a) <= 0 && 0 < y(b))
            if (cross(a, b) < 0) in = !in;
        if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
    }
    return in ? IN : OUT;
}
// 点が円の中にあるか判定
bool contains(const P& p, const C& c) {
    return abs(p - c.p) < c.r + EPS;
}
// 円と線分の位置関係(返り値が正なら当たっている) positional relation
int posRel(const L& s, const C& c) {
    if (abs(distanceSP(s, c.p) - c.r) < EPS) return 1;    // 接してる
    if (distanceSP(s, c.p) > c.r + EPS) return 0;         // かすってもない
    if (contains(s[0], c) && contains(s[1], c)) return 2; // 円に内包
    if (contains(s[0], c) || contains(s[1], c)) return 3; // 片側だけ円の中
    return 4;                                             // 円を貫通
}

void solve() {
    int x, y, r;
    cin >> x >> y >> r;
    if (x < 0) x = -x;
    if (y < 0) y = -y;
    C c(P{(D)x, (D)y}, r);
    auto jd = [&](ll mid) {
        L l(P{(D)0, (D)mid}, P{(D)mid, (D)0});
        return posRel(l, c) == 0;
    };
    ll ng = x + y, ok = 1e9;
    while (ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        if (jd(mid)) ok = mid;
        else ng = mid;
    }
    cout << ok << "\n";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    // multi-testcase
    // cin >> t;
    rep(ti, t) solve();
    return 0;
}