#include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; namespace emthrm { template // B = 10^{LOG_B} struct BigInt { int sgn; std::vector data; BigInt(const long long val = 0) { *this = val; } BigInt(const std::string& s) { *this = s; } std::vector convert_base(const int next_log_b, const int next_b) const { assert(next_b == std::llround(std::pow(10, next_log_b))); const int max_base = std::max(LOG_B, next_log_b); std::vector p(max_base + 1, 1); for (int i = 1; i <= max_base; ++i) { p[i] = p[i - 1] * 10; } std::vector res; long long cur_val = 0; int cur_log_b = 0; for (const int e : data) { cur_val += p[cur_log_b] * e; cur_log_b += LOG_B; for (; cur_log_b >= next_log_b; cur_log_b -= next_log_b) { res.emplace_back(cur_val % next_b); cur_val /= next_b; } } res.emplace_back(cur_val); while (!res.empty() && res.back() == 0) res.pop_back(); return res; } int digit_sum() const { assert(sgn == 1); int res = 0; for (char c : to_string()) res += c - '0'; return res; } int length() const { if (data.empty()) return 0; int res = LOG_B * (data.size() - 1); for (int tmp = data.back(); tmp > 0; tmp /= 10) { ++res; } return res; } BigInt pow(BigInt exponent) const { BigInt res = 1, tmp = *this; for (; exponent > 0; exponent /= 2) { if (exponent.data.front() & 1) res *= tmp; tmp *= tmp; } return res; } long long to_llong() const { assert(*this >= std::numeric_limits::min() && *this <= std::numeric_limits::max()); long long res = 0; for (int i = std::ssize(data) - 1; i >= 0; --i) { res = res * B + data[i]; } return res; } std::string to_string() const { std::stringstream ss; ss << *this; std::string res; ss >> res; return res; } void trim() { while (!data.empty() && data.back() == 0) data.pop_back(); if (data.empty()) sgn = 1; } BigInt& operator=(long long val) { if (val < 0) { sgn = -1; val = -val; } else { sgn = 1; } data.clear(); for (; val > 0; val /= B) { data.emplace_back(val % B); } return *this; } BigInt& operator=(const std::string& s) { sgn = 1; data.clear(); if (!s.empty()) { int tail = 0; if (s.front() == '-') { sgn = -1; tail = 1; } else if (s.front() == '+') { tail = 1; } for (int i = s.length() - 1; i >= tail; i -= LOG_B) { int val = 0; for (int j = std::max(tail, i - LOG_B + 1); j <= i; ++j) { val = val * 10 + (s[j] - '0'); } data.emplace_back(val); } } trim(); return *this; } BigInt& operator=(const BigInt& x) = default; BigInt& operator+=(const BigInt& x) { if (sgn != x.sgn) return x.data.empty() ? *this : *this -= -x; if (data.size() < x.data.size()) data.resize(x.data.size(), 0); bool carry = false; for (int i = 0; std::cmp_less(i, x.data.size()) || carry; ++i) { if (std::cmp_equal(i, data.size())) data.emplace_back(0); data[i] += (std::cmp_less(i, x.data.size()) ? x.data[i] : 0) + carry; if (data[i] >= B) { carry = true; data[i] -= B; } else { carry = false; } } return *this; } BigInt& operator-=(const BigInt& x) { if (sgn != x.sgn) return *this += -x; if ((sgn == 1 ? *this : -*this) < (x.sgn == 1 ? x : -x)) { return *this = -(x - *this); } bool carry = false; for (int i = 0; std::cmp_less(i, data.size()) || carry; ++i) { data[i] -= (std::cmp_less(i, x.data.size()) ? x.data[i] : 0) + carry; if (data[i] < 0) { carry = true; data[i] += B; } else { carry = false; } } trim(); return *this; } BigInt& operator*=(const BigInt& x) { constexpr int next_log_b = 6, next_b = 1000000; std::vector this6 = convert_base(next_log_b, next_b); std::vector x6 = x.convert_base(next_log_b, next_b); std::vector res = karatsuba(&this6, 0, this6.size(), &x6, 0, x6.size()); for (int i = 0; std::cmp_less(i, res.size()); ++i) { const long long quo = res[i] / next_b; if (quo > 0) { if (std::cmp_equal(i + 1, res.size())) { res.emplace_back(quo); } else { res[i + 1] += quo; } res[i] %= next_b; } } std::string s = (sgn * x.sgn == 1 ? "+" : "-"); for (int i = std::ssize(res) - 1; i >= 0; --i) { const std::string tmp = std::to_string(res[i]); s += std::string(next_log_b - tmp.length(), '0') + tmp; } return *this = s; } BigInt& operator/=(const int x) { return *this = divide(x).first; } BigInt& operator/=(const BigInt& x) { return *this = divide(x).first; } BigInt& operator%=(const int x) { return *this = divide(x).second; } BigInt& operator%=(const BigInt& x) { return *this = divide(x).second; } std::strong_ordering operator<=>(const BigInt& x) const { if (sgn != x.sgn) return sgn <=> x.sgn; if (data.size() != x.data.size()) { return sgn * data.size() <=> x.sgn * x.data.size(); } for (int i = std::ssize(data) - 1; i >= 0; --i) { if (data[i] != x.data[i]) return data[i] * sgn <=> x.data[i] * x.sgn; } return std::strong_ordering::equivalent; } bool operator==(const BigInt& x) const { if (sgn != x.sgn || data.size() != x.data.size()) return false; const int n = data.size(); for (int i = 0; i < n; ++i) { if (data[i] != x.data[i]) return false; } return true; } BigInt& operator++() { return *this += 1; } BigInt operator++(int) { const BigInt res = *this; ++*this; return res; } BigInt& operator--() { return *this -= 1; } BigInt operator--(int) { const BigInt res = *this; --*this; return res; } BigInt operator+() const { return *this; } BigInt operator-() const { BigInt res = *this; if (!res.data.empty()) res.sgn = -res.sgn; return res; } BigInt operator+(const BigInt& x) const { return BigInt(*this) += x; } BigInt operator-(const BigInt& x) const { return BigInt(*this) -= x; } BigInt operator*(const BigInt& x) const { return BigInt(*this) *= x; } BigInt operator/(const int x) const { return BigInt(*this) /= x; } BigInt operator/(const BigInt& x) const { return BigInt(*this) /= x; } BigInt operator%(const int x) const { return BigInt(*this) %= x; } BigInt operator%(const BigInt& x) const { return BigInt(*this) %= x; } friend std::ostream& operator<<(std::ostream& os, const BigInt& x) { if (x.sgn == -1) os << '-'; os << (x.data.empty() ? 0 : x.data.back()); for (int i = std::ssize(x.data) - 2; i >= 0; --i) { os << std::setw(LOG_B) << std::setfill('0') << x.data[i]; } return os; } friend std::istream& operator>>(std::istream& is, BigInt& x) { std::string s; is >> s; x = s; return is; } private: std::vector karatsuba( std::vector* a, const int a_l, const int a_r, std::vector* b, const int b_l, const int b_r) const { const int a_len = a_r - a_l, b_len = b_r - b_l; if (a_len < b_len) return karatsuba(b, b_l, b_r, a, a_l, a_r); std::vector res(a_len + b_len, 0); if (b_len <= 32) { for (int i = a_l; i < a_r; ++i) { for (int j = b_l; j < b_r; ++j) { res[(i - a_l) + (j - b_l)] += (*a)[i] * (*b)[j]; } } } else { const int mid = (a_len + 1) / 2, n = std::min(b_len, mid); for (int i = a_l; i + mid < a_r; ++i) { (*a)[i] += (*a)[i + mid]; } for (int i = b_l; i + mid < b_r; ++i) { (*b)[i] += (*b)[i + mid]; } std::ranges::copy(karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n), std::next(res.begin(), mid)); for (int i = a_l; i + mid < a_r; ++i) { (*a)[i] -= (*a)[i + mid]; } for (int i = b_l; i + mid < b_r; ++i) { (*b)[i] -= (*b)[i + mid]; } std::vector tmp = karatsuba(a, a_l, a_l + mid, b, b_l, b_l + n); for (int i = 0; std::cmp_less(i, tmp.size()); ++i) { res[i] += tmp[i]; res[mid + i] -= tmp[i]; } tmp = karatsuba(a, a_l + mid, a_r, b, b_l + n, b_r); for (int i = 0; std::cmp_less(i, tmp.size()); ++i) { res[mid + i] -= tmp[i]; res[(mid << 1) + i] += tmp[i]; } } while (!res.empty() && res.back() == 0) res.pop_back(); return res; } std::pair divide(int x) const { assert(x != 0); BigInt dividend = *this; if (x < 0) { dividend.sgn = -dividend.sgn; x = -x; } long long rem = 0; for (int i = std::ssize(dividend.data) - 1; i >= 0; --i) { const long long tmp = rem * B + dividend.data[i]; dividend.data[i] = tmp / x; rem = tmp % x; } dividend.trim(); return {dividend, static_cast(rem)}; } std::pair divide(const BigInt& x) const { assert(!x.data.empty()); const int k = B / (x.data.back() + 1); const BigInt dividend = (sgn == 1 ? *this : -*this) * k; const BigInt divisor = (x.sgn == 1 ? x : -x) * k; BigInt quo, rem = 0; quo.data.resize(dividend.data.size()); const int n = divisor.data.size(); for (int i = std::ssize(dividend.data) - 1; i >= 0; --i) { rem.data.emplace(rem.data.begin(), dividend.data[i]); quo.data[i] = ((std::cmp_less(n, rem.data.size()) ? static_cast(rem.data[n]) * B : 0) + (std::cmp_less(n - 1, rem.data.size()) ? rem.data[n - 1] : 0)) / divisor.data.back(); rem -= divisor * quo.data[i]; while (rem.sgn == -1) { rem += divisor; --quo.data[i]; } } quo.sgn = sgn * x.sgn; quo.trim(); rem.sgn = sgn; rem.trim(); return {quo, rem / k}; } }; } // namespace emthrm namespace std { template emthrm::BigInt gcd(emthrm::BigInt a, emthrm::BigInt b) { while (!b.data.empty()) std::swap(a %= b, b); return a; } template emthrm::BigInt lcm(const emthrm::BigInt& a, const emthrm::BigInt& b) { return a / std::__gcd(a, b) * b; } template emthrm::BigInt abs(const emthrm::BigInt& x) { return x.sgn == 1 ? x : -x; } template emthrm::BigInt max(const emthrm::BigInt& a, const emthrm::BigInt& b) { return a < b ? b : a; } template emthrm::BigInt min(const emthrm::BigInt& a, const emthrm::BigInt& b) { return a < b ? a : b; } } // namespace std template struct Rational { T num, den; Rational() : num(0), den(1) {} Rational(const T num, const T den = 1) : num(num), den(den) { // assert(den != 0); reduce(); } template Real to_real() const { return static_cast(num) / den; } Rational& operator+=(const Rational& x) { const T g = std::gcd(den, x.den); num = num * (x.den / g) + x.num * (den / g); den *= x.den / g; reduce(); return *this; } Rational& operator-=(const Rational& x) { return *this += -x; } Rational& operator*=(const Rational& x) { const T g1 = std::gcd(num, x.den), g2 = std::gcd(den, x.num); num = (num / g1) * (x.num / g2); den = (den / g2) * (x.den / g1); reduce(); return *this; } Rational& operator/=(const Rational& x) { return *this *= Rational(x.den, x.num); } auto operator<=>(const Rational& x) const { return num * x.den <=> x.num * den; } bool operator==(const Rational& x) const { return num == x.num && den == x.den; } Rational& operator++() { if ((num += den) == 0) den = 1; return *this; } Rational operator++(int) { const Rational res = *this; ++*this; return res; } Rational& operator--() { if ((num -= den) == 0) den = 1; return *this; } Rational operator--(int) { const Rational res = *this; --*this; return res; } Rational operator+() const { return *this; } Rational operator-() const { return Rational(-num, den); } Rational operator+(const Rational& x) const { return Rational(*this) += x; } Rational operator-(const Rational& x) const { return Rational(*this) -= x; } Rational operator*(const Rational& x) const { return Rational(*this) *= x; } Rational operator/(const Rational& x) const { return Rational(*this) /= x; } friend std::ostream& operator<<(std::ostream& os, const Rational& x) { if (x.den == 1) return os << x.num; return os << x.num << '/' << x.den; } private: void reduce() { const T g = std::gcd(num, den); num /= g; den /= g; if (den < 0) { num = -num; den = -den; } } }; using bigint = emthrm::BigInt<>; using rational = Rational; using Point = pair; tuple smallest_enclosing_circle( const Point& p1, const Point& p2, const Point& p3) { const auto get_circle = [](const Point& p1, const Point& p2) -> tuple { const auto [p1x, p1y] = p1; const auto [p2x, p2y] = p2; return {rational(p1x + p2x, 2), rational(p1y + p2y, 2), rational((p2x - p1x) * (p2x - p1x) + (p2y - p1y) * (p2y - p1y), 4)}; }; auto [cx, cy, cr] = get_circle(p1, p2); const auto is_in = [&](const Point& p) -> bool { const auto [x, y] = p; return (cx - bigint{x}) * (cx - bigint{x}) + (cy - bigint{y}) * (cy - bigint{y}) <= cr; }; if (!is_in(p3)) { tie(cx, cy, cr) = get_circle(p1, p3); if (!is_in(p2)) { tie(cx, cy, cr) = get_circle(p2, p3); if (!is_in(p1)) { const int a = (p3.first - p2.first) * (p3.first - p2.first) + (p3.second - p2.second) * (p3.second - p2.second); const int b = (p1.first - p3.first) * (p1.first - p3.first) + (p1.second - p3.second) * (p1.second - p3.second); const int c = (p2.first - p1.first) * (p2.first - p1.first) + (p2.second - p1.second) * (p2.second - p1.second); const int idx = p3.first - p1.first, idy = p3.second - p1.second; const int jdx = p2.first - p1.first, jdy = p2.second - p1.second; const int s = idx * jdy - idy * jdx; cx = rational(bigint{p1.first} * a * (b + c - a) + bigint{p2.first} * b * (c + a - b) + bigint{p3.first} * c * (a + b - c), 4LL * s * s); cy = rational(bigint{p1.second} * a * (b + c - a) + bigint{p2.second} * b * (c + a - b) + bigint{p3.second} * c * (a + b - c), 4LL * s * s); cr = (cx - bigint{p1.first}) * (cx - bigint{p1.first}) + (cy - bigint{p1.second}) * (cy - bigint{p1.second}); } } } return {cx, cy, cr}; } int main() { int q, xa, ya, xb, yb, xc, yc; cin >> q >> xa >> ya >> xb >> yb >> xc >> yc; const auto [cx, cy, cr] = smallest_enclosing_circle({xa, ya}, {xb, yb}, {xc, yc}); while (q--) { int x, y; cin >> x >> y; cout << ((cx - bigint{x}) * (cx - bigint{x}) + (cy - bigint{y}) * (cy - bigint{y}) <= cr ? "Yes\n" : "No\n"); } return 0; }