結果

問題 No.2602 Real Collider
ユーザー 寝癖
提出日時 2024-07-15 16:07:48
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37 WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

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