結果
| 問題 |
No.2602 Real Collider
|
| コンテスト | |
| ユーザー |
 coindarw
|
| 提出日時 | 2024-01-14 00:10:46 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 23,423 bytes |
| コンパイル時間 | 5,006 ms |
| コンパイル使用メモリ | 319,784 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-09-28 01:50:03 |
| 合計ジャッジ時間 | 10,331 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 WA * 43 |
ソースコード
#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 = __float128;
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);
using Vector = Geometry::VectorI;
Vector v1 = Vector(_xb - _xa, _yb - _ya);
Vector v2 = Vector(_xc - _xa, _yc - _ya);
ll cross = Geometry::cross(v1, v2);
if (cross == 0) {
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) {
xo = (xa + xb) / 2;
yo = (ya + yb) / 2;
rSq = (xa - xo) * (xa - xo) + (ya - yo) * (ya - yo);
} else if (ac >= ab && ac >= bc) {
xo = (xa + xc) / 2;
yo = (ya + yc) / 2;
rSq = (xa - xo) * (xa - xo) + (ya - yo) * (ya - yo);
} else {
xo = (xb + xc) / 2;
yo = (yb + yc) / 2;
rSq = (xb - xo) * (xb - xo) + (yb - yo) * (yb - yo);
}
}
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) {
oup("Yes");
} else {
oup("No");
}
}
return 0;
}