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

提出ソース
結果

問題	No.2602 Real Collider
ユーザー	coindarw
提出日時	2024-01-14 00:44:35
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	23,903 bytes
コンパイル時間	5,059 ms
コンパイル使用メモリ	319,704 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-28 01:53:37
合計ジャッジ時間	9,632 ms
ジャッジサーバーID （参考情報）	judge5 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	51 ms 5,376 KB
testcase_11	AC	20 ms 5,376 KB
testcase_12	AC	25 ms 5,376 KB
testcase_13	AC	14 ms 5,376 KB
testcase_14	AC	29 ms 5,376 KB
testcase_15	WA	-
testcase_16	AC	23 ms 5,376 KB
testcase_17	WA	-
testcase_18	AC	17 ms 5,376 KB
testcase_19	AC	22 ms 5,376 KB
testcase_20	WA	-
testcase_21	AC	18 ms 5,376 KB
testcase_22	AC	20 ms 5,376 KB
testcase_23	AC	14 ms 5,376 KB
testcase_24	AC	20 ms 5,376 KB
testcase_25	AC	20 ms 5,376 KB
testcase_26	WA	-
testcase_27	AC	23 ms 5,376 KB
testcase_28	WA	-
testcase_29	AC	21 ms 5,376 KB
testcase_30	AC	22 ms 5,376 KB
testcase_31	AC	23 ms 5,376 KB
testcase_32	AC	19 ms 5,376 KB
testcase_33	WA	-
testcase_34	AC	23 ms 5,376 KB
testcase_35	AC	15 ms 5,376 KB
testcase_36	WA	-
testcase_37	AC	24 ms 5,376 KB
testcase_38	AC	26 ms 5,376 KB
testcase_39	AC	25 ms 5,376 KB
testcase_40	WA	-
testcase_41	AC	28 ms 5,376 KB
testcase_42	WA	-
testcase_43	WA	-
testcase_44	AC	28 ms 5,376 KB
testcase_45	AC	17 ms 5,376 KB
testcase_46	AC	18 ms 5,376 KB
testcase_47	AC	25 ms 5,376 KB
testcase_48	AC	19 ms 5,376 KB
testcase_49	AC	18 ms 5,376 KB
testcase_50	WA	-
testcase_51	WA	-
testcase_52	AC	10 ms 5,376 KB
testcase_53	AC	24 ms 5,376 KB
testcase_54	AC	19 ms 5,376 KB
testcase_55	WA	-
testcase_56	WA	-
testcase_57	AC	19 ms 5,376 KB
testcase_58	AC	8 ms 5,376 KB
testcase_59	AC	22 ms 5,376 KB
testcase_60	WA	-
testcase_61	WA	-
testcase_62	AC	23 ms 5,376 KB
testcase_63	WA	-
testcase_64	AC	31 ms 5,376 KB
testcase_65	WA	-
testcase_66	AC	26 ms 5,376 KB
testcase_67	AC	12 ms 5,376 KB
testcase_68	AC	14 ms 5,376 KB
testcase_69	AC	10 ms 5,376 KB
testcase_70	AC	12 ms 5,376 KB
testcase_71	AC	16 ms 5,376 KB
testcase_72	WA	-
testcase_73	WA	-
testcase_74	AC	22 ms 5,376 KB
testcase_75	WA	-
testcase_76	AC	21 ms 5,376 KB
testcase_77	AC	22 ms 5,376 KB
testcase_78	AC	28 ms 5,376 KB
testcase_79	AC	23 ms 5,376 KB
testcase_80	AC	28 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef ONLINE_JUDGE
#include <bits/stdc++.h>

#include <atcoder/all>
#else
#include <mylibs/all.h>
#endif

using ll = long long;
using lll = __int128_t;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define length(v) ((int)(v).size())
constexpr int inf = 2'000'000'000;
constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using namespace atcoder;

// clang-format off
#define Vec(type, ...) __make_vec<type>(__VA_ARGS__)
template <class T> vector<T> __make_vec(size_t a) {return vector<T>(a);}template <class T, class... Ts>
auto __make_vec(size_t a, Ts... ts) {return vector<decltype(__make_vec<T>(ts...))>(a, __make_vec<T>(ts...));}
#define VecI(init, type, ...) __make_vecI<type, init>(__VA_ARGS__)
template <class T, T init>vector<T> __make_vecI(size_t a) {return vector<T>(a, init);}
template <class T, T init, class... Ts>
auto __make_vecI(size_t a, Ts... ts) {return vector<decltype(__make_vecI<T, init>(ts...))>(a, __make_vecI<T, init>(ts...));}

template <typename T, typename U>inline ostream& operator<<(ostream& os, const pair<T, U>& p) noexcept {return os << p.first << " " << p.second;}
inline ostream& operator<<(ostream& os, const modint& m) noexcept { return os << m.val(); }
template <int M>inline ostream& operator<<(ostream& os, const static_modint<M>& m) noexcept { return os << m.val(); }

template <typename T> struct is_static_modint : std::false_type {}; template <int MOD> struct is_static_modint<static_modint<MOD>> : std::true_type {};
template <template <typename...> typename C, typename Number>concept MyContainer = std::is_same_v<C<Number>, std::vector<Number>> || std::is_same_v<C<Number>, std::deque<Number>> || std::is_same_v<C<Number>, std::set<Number>> || std::is_same_v<C<Number>, std::unordered_set<Number>> || std::is_same_v<C<Number>, std::unordered_multiset<Number>> || std::is_same_v<C<Number>, std::multiset<Number>>;
template <typename Number>concept MyNumber = std::is_same_v<Number, int> || std::is_same_v<Number, ll> || std::is_same_v<Number, char> || std::is_same_v<Number, modint> || is_static_modint<Number>::value;
template <template <typename...> typename C, typename Number>concept MyContainerNumber = MyContainer<C, Number> && MyNumber<Number>;
template <template <typename...> typename OutCon, template <typename...> typename InCon, typename Number>concept MyNestedContainerNumber = MyContainer<OutCon, InCon<Number>> && MyContainerNumber<InCon, Number>;
template <template <typename...> typename C, typename Number>requires MyContainerNumber<C, Number>std::ostream& operator<<(std::ostream& os, const C<Number>& t) {auto itr = t.begin();auto end = t.end();if (itr != end) {os << *itr++;for (; itr != end; ++itr) os << ' ' << *itr;}return os;}
template <template <typename...> typename OutCon, template <typename...> typename InCon, typename Number>requires MyNestedContainerNumber<OutCon, InCon, Number>std::ostream& operator<<(std::ostream& os, const OutCon<InCon<Number>>& t) {auto itr = t.begin();auto end = t.end();if (itr != end) {os << *itr++;for (; itr != end; ++itr) os << '\n' << *itr;}return os;}
template <typename T, typename U>istream& operator>>(istream& is, pair<T, U>& p) {return is >> p.first >> p.second;}
template <typename T>istream& operator>>(istream& is, vector<T>& v) {for (auto& e : v) is >> e;return is;}
void inp() {}
template <typename T, typename... Args>void inp(T& a, Args&... args) {cin >> a, inp(args...);}
template <typename T>void inp1(vector<T>& v, int offset = 1, int len = -1) {if (len == -1) len = int(v.size()) - offset;assert(offset >= 0 && len >= 0);for (int i = offset; i < offset + len; ++i) cin >> v[i];}
template <typename T>void oup(const T& a) {cout << a << "\n";}
template <typename T, typename... Args>void oup(const T& a, const Args&... args) {cout << a << " ", oup(args...);}

inline string YESNO(bool cond) { return cond ? "YES" : "NO"; }inline string yesno(bool cond) { return cond ? "yes" : "no"; }inline string YesNo(bool cond) { return cond ? "Yes" : "No"; }
inline auto add1(auto vec, ll offset = 1) {for (auto& e : vec) e += offset;return vec;}
#ifdef ONLINE_JUDGE
#define debug(...)
#else
#define debug(...) cerr << "<" << #__VA_ARGS__ << ">: ", debug_out(__VA_ARGS__)
template <typename T>void debug_out(T t) {cerr << t << "\n";}
template <typename T, typename... Args>void debug_out(T t, Args... args) {cerr << t << ", ";debug_out(args...);}
#endif

#ifdef ONLINE_JUDGE
#define todo(...) static_assert(false)
#else
#define todo(...)
#endif
// clang-format on

class Geometry {
    constexpr static double eps = 1e-10;

   public:
    enum {
        COUNTER_CLOCKWISE = 1,
        CLOCKWISE = -1,
        ONLINE_BACK = 2,
        ONLINE_FRONT = -2,
        ON_SEGMENT = 0,
    };
    class PointF;
    class PointI {  // integer
       public:
        ll x, y;
        constexpr PointI(ll x = 0, ll y = 0) : x(x), y(y) {}
        constexpr PointI(PointF p) : x(p.x), y(p.y) {}
        constexpr PointI operator+(const PointI& p) const { return PointI(x + p.x, y + p.y); }
        constexpr PointI operator-(const PointI& p) const { return PointI(x - p.x, y - p.y); }
        constexpr PointI operator-() const { return PointI(-x, -y); }
        constexpr PointI operator*(ll a) const { return PointI(a * x, a * y); }
        constexpr PointI operator/(ll a) const { return PointI(x / a, y / a); }
        constexpr PointI reduced() const {
            if (x == 0 && y == 0) return PointI(0, 0);
            ll g = gcd(x, y) * ((y < 0 || (y == 0 && x < 0)) ? -1 : 1);
            return PointI(x / g, y / g);
        }
        constexpr ll sqrMagnitude() const { return x * x + y * y; }
        constexpr double magnitude() const { return sqrt(sqrMagnitude()); }
        constexpr bool operator<(const PointI& p) const { return x != p.x ? x < p.x : y < p.y; }
        constexpr bool operator==(const PointI& p) const { return (x == p.x) && (y == p.y); }
        constexpr friend PointI operator*(ll a, const PointI& p) { return p * a; }
        friend std::ostream& operator<<(std::ostream& os, const PointI& p) noexcept { return os << p.x << " " << p.y; }
        friend std::istream& operator>>(std::istream& is, PointI& p) noexcept { return is >> p.x >> p.y; }
    };
    class PointF {  // float
       public:
        double x, y;
        constexpr PointF(double x = 0, double y = 0) : x(x), y(y) {}
        constexpr PointF(PointI p) : x(p.x), y(p.y) {}
        constexpr PointF operator+(PointF p) const { return PointF(x + p.x, y + p.y); }
        constexpr PointF operator-(PointF p) const { return PointF(x - p.x, y - p.y); }
        constexpr PointF operator-() const { return PointF(-x, -y); }
        constexpr PointF operator*(double a) const { return PointF(a * x, a * y); }
        constexpr PointF operator/(double a) const { return PointF(x / a, y / a); }
        constexpr PointF normalized() const {
            double a = magnitude();
            return (abs(a) < eps) ? PointF(0, 0) : PointF(x / a, y / a);
        }
        constexpr double sqrMagnitude() const { return x * x + y * y; }
        constexpr double magnitude() const { return sqrt(sqrMagnitude()); }
        constexpr bool operator<(const PointF& p) const { return x != p.x ? x < p.x : y < p.y; }
        constexpr bool operator==(const PointF& p) const { return (fabs(x - p.x) < eps) && (fabs(y - p.y) < eps); }
        constexpr bool operator!=(const PointF& p) const { return !(*this == p); }
        constexpr friend PointF operator*(double a, const PointF& p) { return p * a; }
        friend std::ostream& operator<<(std::ostream& os, const PointF& p) noexcept { return os << p.x << " " << p.y; }
        friend std::istream& operator>>(std::istream& is, PointF& p) noexcept { return is >> p.x >> p.y; }
    };

    struct SegmentI {
        PointI p1, p2;
    };
    struct SegmentF {
        PointF p1, p2;
    };
    using VectorI = PointI;
    using LineI = SegmentI;
    using PolygonI = vector<PointI>;
    using VectorF = PointF;
    using LineF = SegmentF;
    using PolygonF = vector<PointF>;
    // 整数
    constexpr static ll dot(VectorI a, VectorI b) { return a.x * b.x + a.y * b.y; }
    constexpr static ll cross(VectorI a, VectorI b) { return a.x * b.y - a.y * b.x; }
    constexpr static int ccw(PointI p0, PointI p1, PointI p2) {
        VectorI v1 = p1 - p0;
        VectorI v2 = p2 - p0;
        if (cross(v1, v2) > 0) return COUNTER_CLOCKWISE;
        if (cross(v1, v2) < 0) return CLOCKWISE;
        if (dot(v1, v2) < 0) return ONLINE_BACK;
        if (v1.sqrMagnitude() < v2.sqrMagnitude()) return ONLINE_FRONT;
        return ON_SEGMENT;
    }
    constexpr static bool intersect(PointI p1, PointI p2, PointI p3, PointI p4) { return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) && (ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0); }
    constexpr static bool intersect(SegmentI s1, SegmentI s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2); }
    constexpr static bool intersectSL(SegmentI s, LineI l) { return cross(l.p2 - l.p1, s.p1 - l.p1) * cross(l.p2 - l.p1, s.p2 - l.p1) <= 0; }
    constexpr static ll getDistanceSqr(PointI a, PointI b) { return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y); }
    constexpr static double getDistanceLP(LineI l, PointI p) { return fabs(cross(l.p2 - l.p1, p - l.p1)) / (l.p2 - l.p1).magnitude(); }
    constexpr static double getDistanceSP(SegmentI s, PointI p) {
        if (dot(s.p2 - s.p1, p - s.p1) < 0) return (p - s.p1).magnitude();
        if (dot(s.p1 - s.p2, p - s.p2) < 0) return (p - s.p2).magnitude();
        return getDistanceLP(s, p);
    }
    constexpr static double getDistance(SegmentI s1, SegmentI s2) {
        if (intersect(s1, s2)) return 0;
        return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)), min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
    }
    // 凸包を求め、反時計回りで返す
    static PolygonI convexHull(const PolygonI& polygon, bool strict = true) {
        auto ps = polygon;
        sort(all(ps));
        ps.erase(unique(all(ps)), ps.end());
        const int n = ps.size();
        PolygonI qs(n * 2);
        int k = 0;
        for (int i = 0; i < n; ++i) {
            ll cr;
            while (k >= 2 && (cr = cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 2]) < 0 || (strict && cr == 0))) k--;
            qs[k++] = ps[i];
        }
        for (int i = n - 1, t = k + 1; i > 0; --i) {
            ll cr;
            while (k >= t && (cr = cross(qs[k - 1] - qs[k - 2], ps[i - 1] - qs[k - 2]) < 0 || (strict && cr == 0))) k--;
            qs[k++] = ps[i - 1];
        }
        qs.resize(k - 1);
        return qs;
    }
    static ll polygon_area_2(const PolygonI& ps) {
        // 多角形の面積の”2倍”，反時計回りに並んでる必要あり
        ll area = 0;
        const int n = ps.size();
        reps(i, n - 2) { area += cross(ps[i] - ps[0], ps[i + 1] - ps[0]); }
        return area;
    }
    static bool is_convex(const PolygonI& ps) {
        // 凸多角形かどうか
        const int n = ps.size();
        rep(i, n) {
            if (cross(ps[(i + 1) % n] - ps[i], ps[(i + 2) % n] - ps[i]) < 0) return false;
        }
        return true;
    }
    static int in_concave_polygon(const PointI& p, const PolygonI& G) {
        // G: 凸とは限らない多角形、反時計回り, O(n)
        // 0: out, 1: on, 2: in
        int cnt = 0;
        rep(i, G.size()) {
            if (ccw(G[i], G[(i + 1) % G.size()], p) == 0) {
                return 1;
            }
            VectorI v1 = G[i] - p;
            VectorI v2 = G[(i + 1) % G.size()] - p;

            if (v1.y > v2.y) {
                swap(v1, v2);
            }
            if (cross(v1, v2) > 0 && v1.y < 0 && v2.y >= 0) {
                cnt++;
            }
        }
        return (cnt % 2 == 1) ? 2 : 0;
    }
    static ll convexDiameterSqr(const PolygonI& polygon) {
        const int n = polygon.size();
        int is = 0, js = 0;
        reps(i, n - 1) {
            if (polygon[i].y > polygon[is].y) is = i;
            if (polygon[i].y < polygon[js].y) js = i;
        }
        ll maxd = (polygon[is] - polygon[js]).sqrMagnitude();
        int i, maxi, j, maxj;
        i = maxi = is;
        j = maxj = js;
        do {
            if (cross(polygon[(i + 1) % n] - polygon[i], polygon[(j + 1) % n] - polygon[j]) >= 0) {
                j = (j + 1) % n;
            } else {
                i = (i + 1) % n;
            }
            if ((polygon[i] - polygon[j]).sqrMagnitude() > maxd) {
                maxd = (polygon[i] - polygon[j]).sqrMagnitude();
                maxi = i, maxj = j;
            }
        } while (i != is || j != js);
        return maxd;
    }
    // 実数
    constexpr static double dot(VectorF a, VectorF b) { return a.x * b.x + a.y * b.y; }
    constexpr static double cross(VectorF a, VectorF b) { return a.x * b.y - a.y * b.x; }
    constexpr static VectorF projection(PointF p1, PointF p2, PointF p) { return (p2 - p1) * dot(p - p1, p2 - p1) / (p2 - p1).sqrMagnitude(); }
    constexpr static int ccw(PointF p0, PointF p1, PointF p2) {
        VectorF v1 = p1 - p0;
        VectorF v2 = p2 - p0;
        if (cross(v1, v2) > eps) return COUNTER_CLOCKWISE;
        if (cross(v1, v2) < -eps) return CLOCKWISE;
        if (dot(v1, v2) < -eps) return ONLINE_BACK;
        if (v1.sqrMagnitude() < v2.sqrMagnitude()) return ONLINE_FRONT;
        return ON_SEGMENT;
    }
    constexpr static double getDistanceSqr(PointF a, PointF b) { return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y); }
    constexpr static double getDistanceLP(LineF l, PointF p) { return abs(cross(l.p2 - l.p1, p - l.p1)) / (l.p2 - l.p1).magnitude(); }
    constexpr static double getDistanceSP(SegmentF s, PointF p) {
        if (dot(s.p2 - s.p1, p - s.p1) < 0.) return (p - s.p1).magnitude();
        if (dot(s.p1 - s.p2, p - s.p2) < 0.) return (p - s.p2).magnitude();
        return getDistanceLP(s, p);
    }
    constexpr static bool intersect(PointF p1, PointF p2, PointF p3, PointF p4) { return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) && (ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0); }
    constexpr static bool intersect(SegmentF s1, SegmentF s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2); }
    constexpr static bool intersectSL(SegmentF s, LineF l) { return cross(l.p2 - l.p1, s.p1 - l.p1) * cross(l.p2 - l.p1, s.p2 - l.p1) < eps; }

    constexpr static double getDistance(SegmentF s1, SegmentF s2) {
        if (intersect(s1, s2)) return 0;
        return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)), min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
    }
    constexpr static PointF getCrossPoint(SegmentF s1, SegmentF s2) {
        VectorF v1 = s2.p2 - s1.p1;
        VectorF v2 = s2.p1 - s1.p1;
        VectorF v3 = s1.p2 - s2.p1;
        double k = (cross(v2, s1.p1) - cross(v2, s2.p1) + cross(v2, v2) * 2 + cross(v3, s1.p1) - cross(v3, s2.p1) + cross(v3, v2) * 2) / (cross(v1, v2) + cross(v1, v3) - cross(v2, v3));
        return s1.p1 + v1 * k + v2 * (1 - k);
    }
    static double polygon_area_2(const PolygonF& ps) {
        // 多角形の面積の”2倍”，反時計回りに並んでる必要あり
        double area = 0;
        const int n = ps.size();
        reps(i, n - 2) { area += cross(ps[i] - ps[0], ps[i + 1] - ps[0]); }
        return area;
    }
    static bool is_convex(const PolygonF& ps) {
        // 凸多角形かどうか
        const int n = ps.size();
        rep(i, n) {
            if (cross(ps[(i + 1) % n] - ps[i], ps[(i + 2) % n] - ps[i]) < 0) return false;
        }
        return true;
    }
    static bool is_parallel(const LineF& l1, const LineF& l2) {
        // 平行かどうか
        return abs(cross(l1.p2 - l1.p1, l2.p2 - l2.p1)) < eps;
    }
    static int in_concave_polygon(const PointF& p, const PolygonF& G) {
        // G: 凸とは限らない多角形、反時計回り, O(n)
        // 0: out, 1: on, 2: in
        int cnt = 0;
        rep(i, G.size()) {
            if (ccw(G[i], G[(i + 1) % G.size()], p) == 0) {
                return 1;
            }
            VectorF v1 = G[i] - p;
            VectorF v2 = G[(i + 1) % G.size()] - p;

            if (v1.y > v2.y) {
                swap(v1, v2);
            }
            if (cross(v1, v2) > 0 && v1.y < 0 && v2.y >= 0) {
                cnt++;
            }
        }
        return (cnt % 2 == 1) ? 2 : 0;
    }
    // 凸包を求め、反時計回りで返す
    static PolygonF convexHull(const PolygonF& polygon, bool strict = true) {
        auto ps = polygon;
        sort(all(ps));
        ps.erase(unique(all(ps)), ps.end());
        const int n = ps.size();
        PolygonF qs(n * 2);
        int k = 0;
        for (int i = 0; i < n; ++i) {
            double cr;
            while (k >= 2 && (cr = cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 2]) < -eps || (strict && cr < eps))) k--;
            qs[k++] = ps[i];
        }
        for (int i = n - 1, t = k + 1; i > 0; --i) {
            double cr;
            while (k >= t && (cr = cross(qs[k - 1] - qs[k - 2], ps[i - 1] - qs[k - 2]) < -eps || (strict && cr < eps))) k--;
            qs[k++] = ps[i - 1];
        }
        qs.resize(k - 1);
        return qs;
    }
    static double convexDiameter(const PolygonF& polygon) {
        const int n = polygon.size();
        int is = 0, js = 0;
        reps(i, n - 1) {
            if (polygon[i].y > polygon[is].y) is = i;
            if (polygon[i].y < polygon[js].y) js = i;
        }
        double maxd = (polygon[is] - polygon[js]).sqrMagnitude();
        int i, maxi, j, maxj;
        i = maxi = is;
        j = maxj = js;
        do {
            if (cross(polygon[(i + 1) % n] - polygon[i], polygon[(j + 1) % n] - polygon[j]) >= 0) {
                j = (j + 1) % n;
            } else {
                i = (i + 1) % n;
            }
            if ((polygon[i] - polygon[j]).sqrMagnitude() > maxd) {
                maxd = (polygon[i] - polygon[j]).sqrMagnitude();
                maxi = i, maxj = j;
            }
        } while (i != is || j != js);
        return sqrt(maxd);
    }
    static PolygonF convexCut(const PolygonF& polygon, const LineF& l) {
        // 反時計回りに並んだ凸多角形(各内角が180度以下)のpolygonをlによって切断した時の左側(l.p1→p2から見て)の多角形を返す
        PolygonF res;
        auto [p1, p2] = l;
        rep(i, polygon.size()) {
            PointF a = polygon[i], b = polygon[(i + 1) % polygon.size()];
            SegmentF s = {a, b};
            if (ccw(p1, p2, a) != -1) res.push_back(a);
            if (intersectSL(s, l) && !is_parallel(s, l)) {
                auto cp = getCrossPoint({a, b}, {p1, p2});
                if (cp != a && cp != b) res.push_back(cp);
            }
        }
        return res;
    }
    static double closestPair(const vector<PointF>& ps) {
        auto qs = ps;
        sort(all(qs));
        return _closestPair(qs, 0, qs.size());
    }
    // その他
    // 凸多角形の内部に入っているか判定
    struct ConvexPolygonInclude {
        using PolygonI = Geometry::PolygonI;
        using PointI = Geometry::PointI;

       private:
        PolygonI polygon;

       public:
        ConvexPolygonInclude(const PolygonI& _polygon) : polygon(_polygon) {
            assert(polygon.size() >= 3);
            PointI p0 = polygon[0];
            sort(polygon.begin() + 1, polygon.end(), [&](const auto& a, const auto& b) { return Geometry::cross(a - p0, b - p0) > 0; });
        }
        int check(const PointI& p) const {
            // -1 : out, 0 : on, 1 : in
            int c1, c2;
            if ((c1 = ccw(polygon[0], polygon[1], p)) == CLOCKWISE || c1 == ONLINE_BACK || c1 == ONLINE_FRONT || (c2 = ccw(polygon[0], polygon.back(), p)) == COUNTER_CLOCKWISE || c2 == ONLINE_BACK || c2 == ONLINE_FRONT) return -1;
            if (c1 == ON_SEGMENT || c2 == ON_SEGMENT) return 0;
            auto lb = lower_bound(polygon.begin() + 1, polygon.end(), p, [&](const auto& a, const auto& b) { return Geometry::cross(a - polygon[0], b - polygon[0]) > 0; });
            if (lb == polygon.begin() + 1) {
                return -1;
            }
            auto p1 = *(lb - 1);
            auto p2 = *lb;
            int c3 = ccw(p1, p2, p);
            return c3;
        }
    };

   private:
    static double _closestPair(vector<PointF>& ps, int l, int r) {
        const int n = r - l;
        if (n <= 1) return inf;
        int m = n / 2;
        double x = ps[l + m].x;
        double d = min(_closestPair(ps, l, l + m), _closestPair(ps, l + m, r));
        inplace_merge(ps.begin() + l, ps.begin() + l + m, ps.begin() + r, [](const auto& a, const auto& b) { return a.y < b.y; });
        vector<PointF> b;
        rep(i, n) {
            if (fabs(ps[l + i].x - x) >= d) continue;
            rrep(j, b.size()) {
                double dx = ps[l + i].x - b[j].x, dy = ps[l + i].y - b[j].y;
                if (dy >= d) break;
                d = min(d, sqrt(dx * dx + dy * dy));
            }
            b.push_back(ps[l + i]);
        }
        return d;
    }
};

using lf = long double;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    inp(q);
    ll _xa, _ya, _xb, _yb, _xc, _yc;
    inp(_xa, _ya, _xb, _yb, _xc, _yc);
    lf xa = _xa, ya = _ya, xb = _xb, yb = _yb, xc = _xc, yc = _yc;
    lf xo = ((xa * xa + ya * ya) * (yb - yc) + (xb * xb + yb * yb) * (yc - ya) + (xc * xc + yc * yc) * (ya - yb)) / ((xa - xb) * (yb - yc) - (xb - xc) * (ya - yb)) / 2;
    lf yo = ((xa * xa + ya * ya) * (xb - xc) + (xb * xb + yb * yb) * (xc - xa) + (xc * xc + yc * yc) * (xa - xb)) / ((ya - yb) * (xb - xc) - (yb - yc) * (xa - xb)) / 2;
    lf rSq = (xa - xo) * (xa - xo) + (ya - yo) * (ya - yo);

    if (isnan(double(xo)) || isnan(double(yo)) || isnan(double(rSq))) {
        xo = 0, yo = 0, rSq = linf;
    }

    debug(double(xo), double(yo), double(rSq));
    lf ab = (xb - xa) * (xb - xa) + (yb - ya) * (yb - ya);
    lf ac = (xc - xa) * (xc - xa) + (yc - ya) * (yc - ya);
    lf bc = (xc - xb) * (xc - xb) + (yc - yb) * (yc - yb);
    if (ab >= ac && ab >= bc) {
        lf xxo = (xa + xb) / 2;
        lf yyo = (ya + yb) / 2;
        lf rrSq = (xa - xxo) * (xa - xxo) + (ya - yyo) * (ya - yyo);

        lf oc = (xc - xxo) * (xc - xxo) + (yc - yyo) * (yc - yyo);
        if (oc <= rrSq && rSq > rrSq) {
            xo = xxo, yo = yyo, rSq = rrSq;
        }
    }
    if (ac >= ab && ac >= bc) {
        lf xxo = (xa + xc) / 2;
        lf yyo = (ya + yc) / 2;
        lf rrSq = (xa - xxo) * (xa - xxo) + (ya - yyo) * (ya - yyo);

        lf ob = (xb - xxo) * (xb - xxo) + (yb - yyo) * (yb - yyo);
        if (ob <= rrSq && rSq > rrSq) {
            xo = xxo, yo = yyo, rSq = rrSq;
        }
    }
    if (bc >= ab && bc >= ac) {
        lf xxo = (xb + xc) / 2;
        lf yyo = (yb + yc) / 2;
        lf rrSq = (xb - xxo) * (xb - xxo) + (yb - yyo) * (yb - yyo);

        lf oa = (xa - xxo) * (xa - xxo) + (ya - yyo) * (ya - yyo);
        if (oa <= rrSq && rSq > rrSq) {
            xo = xxo, yo = yyo, rSq = rrSq;
        }
    }
    debug(double(xo), double(yo), double(rSq));

    rep(i, q) {
        ll _x, _y;
        inp(_x, _y);
        lf x = _x, y = _y;
        lf dSq = (x - xo) * (x - xo) + (y - yo) * (y - yo);
        // debug(double(dSq), double(rSq));
        if (dSq <= rSq + __float128(1e-15)) {
            oup("Yes");
        } else {
            oup("No");
        }
    }
    return 0;
}
yukicoder

結果

テストケース

ソースコード
