#995176 (C++23) No.2602 Real Collider

提出ソース

結果

問題	No.2602 Real Collider
ユーザー	寝癖
提出日時	2024-07-15 16:07:48
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,323 bytes
コンパイル時間	5,659 ms
コンパイル使用メモリ	309,232 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-07-15 16:08:11
合計ジャッジ時間	21,613 ms
ジャッジサーバーID （参考情報）	judge6 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	178 ms 6,944 KB
testcase_17	AC	198 ms 6,944 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	118 ms 6,940 KB
testcase_27	WA	-
testcase_28	AC	198 ms 6,940 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	179 ms 6,940 KB
testcase_32	AC	155 ms 6,940 KB
testcase_33	WA	-
testcase_34	AC	191 ms 6,940 KB
testcase_35	AC	115 ms 6,940 KB
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	101 ms 6,940 KB
testcase_41	WA	-
testcase_42	AC	175 ms 6,944 KB
testcase_43	AC	175 ms 6,944 KB
testcase_44	AC	228 ms 6,940 KB
testcase_45	AC	143 ms 6,940 KB
testcase_46	AC	132 ms 6,940 KB
testcase_47	WA	-
testcase_48	AC	159 ms 6,944 KB
testcase_49	WA	-
testcase_50	AC	100 ms 6,944 KB
testcase_51	WA	-
testcase_52	AC	76 ms 6,944 KB
testcase_53	AC	182 ms 6,940 KB
testcase_54	AC	135 ms 6,944 KB
testcase_55	AC	169 ms 6,940 KB
testcase_56	AC	159 ms 6,940 KB
testcase_57	AC	143 ms 6,940 KB
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	AC	119 ms 6,940 KB
testcase_62	WA	-
testcase_63	WA	-
testcase_64	AC	243 ms 6,944 KB
testcase_65	AC	119 ms 6,940 KB
testcase_66	WA	-
testcase_67	AC	92 ms 6,940 KB
testcase_68	AC	107 ms 6,944 KB
testcase_69	AC	78 ms 6,940 KB
testcase_70	WA	-
testcase_71	AC	111 ms 6,948 KB
testcase_72	AC	186 ms 6,940 KB
testcase_73	AC	153 ms 6,944 KB
testcase_74	AC	177 ms 6,940 KB
testcase_75	AC	229 ms 6,944 KB
testcase_76	AC	171 ms 6,940 KB
testcase_77	WA	-
testcase_78	AC	221 ms 6,944 KB
testcase_79	AC	185 ms 6,940 KB
testcase_80	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,n-1,-1)
#define rrepi(i,a,b) for(int i=int(a);i>int(b);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep)(__VA_ARGS__)

#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REVERSE(x) reverse(all(x))

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ostream& operator<<(ostream& os, const modint998244353& a) { return os << a.val(); }
ostream& operator<<(ostream& os, const modint1000000007& a) { return os << a.val(); }

template<class T> istream& operator>>(istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (const T& x : vec) os << x << ' '; return os; }

struct Point {
    double x, y;

    Point() = default;
    Point(double x, double y)
        : x(x)
        , y(y) {}

    Point operator+(const Point& rhs) const { return Point(x + rhs.x, y + rhs.y); }
    Point operator-(const Point& rhs) const { return Point(x - rhs.x, y - rhs.y); }
    Point operator*(double scalar) const { return Point(x * scalar, y * scalar); }
    Point operator/(double scalar) const { return Point(x / scalar, y / scalar); }

    double length() const { return std::sqrt(lengthSq()); }
    double lengthSq() const { return x * x + y * y; }
    double distanceFrom(const Point& rhs) const { return (*this - rhs).length(); }
    double distanceFromSq(const Point& rhs) const { return (*this - rhs).lengthSq(); }

    friend Point operator*(double scalar, const Point& rhs) { return Point(scalar * rhs.x, scalar * rhs.y); }
    friend std::istream& operator>>(std::istream& is, Point& rhs) { return is >> rhs.x >> rhs.y; }
};

struct Triangle {
    Point a, b, c;

    Triangle(const Point& a, const Point& b, const Point& c)
        : a(a)
        , b(b)
        , c(c) {}

    double getAngleA() const {
        double
            dist_a = b.distanceFrom(c),
            dist_b = c.distanceFrom(a),
            dist_c = a.distanceFrom(b);
        return std::acos((-dist_a * dist_a + dist_b * dist_b + dist_c * dist_c) / (2 * dist_b * dist_c));
    }

    double getAngleB() const {
        double
            dist_a = b.distanceFrom(c),
            dist_b = c.distanceFrom(a),
            dist_c = a.distanceFrom(b);
        return std::acos((dist_a * dist_a - dist_b * dist_b + dist_c * dist_c) / (2 * dist_c * dist_a));
    }

    double getAngleC() const { return std::acos(-1.0) - getAngleA() - getAngleB(); }

    //重心
    Point getCentroid() const {
        return (a + b + c) / 3;
    }

    //外心
    Point getCircumCenter() const {
        double
            d_a = (b - c).lengthSq(),
            d_b = (c - a).lengthSq(),
            d_c = (a - b).lengthSq(),
            t_a = d_a * (-d_a + d_b + d_c),
            t_b = d_b * (d_a - d_b + d_c),
            t_c = d_c * (d_a + d_b - d_c),
            s = t_a + t_b + t_c;

        return t_a / s * a + t_b / s * b + t_c / s * c;
    }

    //内心
    Point getInnerCenter() const {
        double 
            dist_a = b.distanceFrom(c),
            dist_b = c.distanceFrom(a),
            dist_c = a.distanceFrom(b);
        return (dist_a * a + dist_b * b + dist_c * c) / (dist_a + dist_b + dist_c);
    }

    //垂心
    Point getOrthoCenter() const {
        return a + b + c - 2 * getCircumCenter();
    }

    //傍心 A
    Point getExcenterA() const {
        double
            dist_a = b.distanceFrom(c),
            dist_b = c.distanceFrom(a),
            dist_c = a.distanceFrom(b);
        return (-dist_a * a + dist_b * b + dist_c * c) / (-dist_a + dist_b + dist_c);
    }

    //傍心 B
    Point getExcenterB() const {
        double
            dist_a = b.distanceFrom(c),
            dist_b = c.distanceFrom(a),
            dist_c = a.distanceFrom(b);
        return (dist_a * a - dist_b * b + dist_c * c) / (dist_a - dist_b + dist_c);
    }

    //傍心 C
    Point getExcenterC() const {
        double
            dist_a = b.distanceFrom(c),
            dist_b = c.distanceFrom(a),
            dist_c = a.distanceFrom(b);
        return (dist_a * a + dist_b * b - dist_c * c) / (dist_a + dist_b - dist_c);
    }

    friend std::istream& operator>>(std::istream& is, Triangle& rhs) { return is >> rhs.a >> rhs.b >> rhs.c; }
};


int main() {
    int Q;
    cin >> Q;
    Point A, B, C;
    cin >> A >> B >> C;

    Triangle tri(A, B, C);
    Point O = tri.getCircumCenter();
    if (isnan(O.x) || isnan(O.y)) {
        O = tri.getCentroid();
    }
    double r = O.distanceFrom(A);

    rep(i, Q) {
        Point P;
        cin >> P;
        double d = O.distanceFrom(P);
        if (r-d > -1e-5) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

yukicoder

結果

テストケース

ソースコード