結果

問題 No.172 UFOを捕まえろ
ユーザー otogawa
提出日時 2025-04-22 06:09:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,771 bytes
コンパイル時間 2,291 ms
コンパイル使用メモリ 198,200 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-22 06:09:23
合計ジャッジ時間 3,836 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int32_t main()’:
main.cpp:66:20: warning: narrowing conversion of ‘mid’ from ‘ll’ {aka ‘long long int’} to ‘ld’ {aka ‘double’} [-Wnarrowing]
   66 |         pt a = {0, mid}, b = {mid, 0};
      |                    ^~~
main.cpp:66:31: warning: narrowing conversion of ‘mid’ from ‘ll’ {aka ‘long long int’} to ‘ld’ {aka ‘double’} [-Wnarrowing]
   66 |         pt a = {0, mid}, b = {mid, 0};
      |                               ^~~
main.cpp:67:43: warning: narrowing conversion of ‘x’ from ‘ll’ {aka ‘long long int’} to ‘ld’ {aka ‘double’} [-Wnarrowing]
   67 |         auto v = circ_line_inter(a, b, pt{x, y}, r);
      |                                           ^
main.cpp:67:46: warning: narrowing conversion of ‘y’ from ‘ll’ {aka ‘long long int’} to ‘ld’ {aka ‘double’} [-Wnarrowing]
   67 |         auto v = circ_line_inter(a, b, pt{x, y}, r);
      |                                              ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int ll
using ll = long long;

typedef double ld;
const ld DINF = 1e18;
const ld pi = acos(-1.0);
const ld eps = 1e-9;

#define sq(x) ((x)*(x))

bool eq(ld a, ld b) {
	return abs(a - b) <= eps;
}

struct pt { // ponto
	ld x, y;
	pt(ld x_ = 0, ld y_ = 0) : x(x_), y(y_) {}
	bool operator < (const pt p) const {
		if (!eq(x, p.x)) return x < p.x;
		if (!eq(y, p.y)) return y < p.y;
		return 0;
	}
	bool operator == (const pt p) const {
		return eq(x, p.x) and eq(y, p.y);
	}
	pt operator + (const pt p) const { return pt(x+p.x, y+p.y); }
	pt operator - (const pt p) const { return pt(x-p.x, y-p.y); }
	pt operator * (const ld c) const { return pt(x*c  , y*c  ); }
	pt operator / (const ld c) const { return pt(x/c  , y/c  ); }
	ld operator * (const pt p) const { return x*p.x + y*p.y; }
	ld operator ^ (const pt p) const { return x*p.y - y*p.x; }
	friend istream& operator >> (istream& in, pt& p) {
		return in >> p.x >> p.y;
	}
};

vector<pt> circ_line_inter(pt a, pt b, pt c, ld r) { // intersecao da circunf (c, r) e reta ab
	vector<pt> ret;
	b = b-a, a = a-c;
	ld A = b*b;
	ld B = a*b;
	ld C = a*a - r*r;
	ld D = B*B - A*C;
	if (D < -eps) return ret;
	ret.push_back(c+a+b*(-B+sqrt(D+eps))/A);
	if (D > eps) ret.push_back(c+a+b*(-B-sqrt(D))/A);
	return ret;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int x, y, r;
    cin >> x >> y >> r;

    if (x) x = x * x / abs(x);
    if (y) y = y * y / abs(y);

    int lo = x + y, hi = 1e9;
    while (lo < hi) {
        int mid = (lo + hi) / 2;

        pt a = {0, mid}, b = {mid, 0};
        auto v = circ_line_inter(a, b, pt{x, y}, r);

        if (v.empty())
            hi = mid;
        else
            lo = mid + 1;
    }

    cout << lo << endl;
}
0