#include using namespace std; #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(n) for(int i = 0; i < (int)(n); ++i) #define rep2(i, n) for(int i = 0; i < (int)(n); ++i) #define rep3(i, a, b) for(int i = (a); i < (int)(b); ++i) #define rep4(i, a, b, c) for(int i = (a); i < (int)(b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; --i) #define ALL(a) (a).begin(), (a).end() #define Sort(a) (sort((a).begin(), (a).end())) #define RSort(a) (sort((a).rbegin(), (a).rend())) #define UNIQUE(a) (a.erase(unique((a).begin(), (a).end()), (a).end())) typedef long long int ll; typedef unsigned long long ul; typedef long double ld; typedef vector vi; typedef vector vll; typedef vector vc; typedef vector vst; typedef vector vd; typedef vector vld; typedef pair P; template long long sum(const T& a){ return accumulate(a.begin(), a.end(), 0LL); } template auto min(const T& a){ return *min_element(a.begin(), a.end()); } template auto max(const T& a){ return *max_element(a.begin(), a.end()); } const long long MINF = 0x7fffffffffff; const long long INF = 0x1fffffffffffffff; const long long MOD = 998244353; const long double EPS = 1e-9; const long double PI = acos(-1); template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template istream &operator>>(istream &is, pair &p){ is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const pair &p){ os << "(" << p.first << ", " << p.second << ")"; return os; } template istream &operator>>(istream &is, vector &v){ for(T &in : v) is >> in; return is; } template ostream &operator<<(ostream &os, const vector &v){ for(int i = 0; i < (int) v.size(); ++i){ os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const map &mp){ for(auto &[key, val] : mp){ os << key << ":" << val << " "; } return os; } template ostream &operator<<(ostream &os, const set &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, const multiset &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, queue q){ while(q.size()){ os << q.front() << " "; q.pop(); } return os; } template ostream &operator<<(ostream &os, deque q){ while(q.size()){ os << q.front() << " "; q.pop_front(); } return os; } template ostream &operator<<(ostream &os, stack st){ while(st.size()){ os << st.top() << " "; st.pop(); } return os; } template ostream &operator<<(ostream &os, priority_queue pq){ while(pq.size()){ os << pq.top() << " "; pq.pop(); } return os; } template inline T vin(T& vec, U n) { vec.resize(n); for(int i = 0; i < (int) n; ++i) cin >> vec[i]; return vec; } template inline void vout(T vec, string s = "\n"){ for(auto x : vec) cout << x << s; } template void in(T&... a){ (cin >> ... >> a); } void out(){ cout << '\n'; } template void out(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } template void inGraph(vector>& G, U n, U m, bool directed = false){ G.resize(n); for(int i = 0; i < m; ++i){ int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); if(!directed) G[b].push_back(a); } } template struct BigInt{ int sign = 1; vector val; constexpr BigInt(const long long _val = 0) noexcept { if(_val != 0){ val.assign(1, abs(_val)); shift(); } if(_val < 0) sign = -1; } constexpr BigInt(const vector &_val) noexcept : val(_val) {} constexpr BigInt(const string &s) noexcept { stoi(s); } private: void normalize(){ while(!val.empty() && val.back() == 0) val.pop_back(); if(val.empty()) sign = 1; } vector karatsuba_algorithm(vector &a, vector &b){ const int n = (int) a.size(); const int h = n >> 1; assert(a.size() == b.size()); assert((n & (n - 1)) == 0); if(n <= 64){ vector res(2 * n - 1); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ res[i + j] += a[i] * b[j]; } } return res; } vector p(h), q(h), r(h), s(h), t(h), u(h); for(int i = 0; i < h; ++i){ p[i] = a[i + h]; q[i] = a[i]; r[i] = b[i + h]; s[i] = b[i]; t[i] = p[i] + q[i]; u[i] = r[i] + s[i]; } p = karatsuba_algorithm(p, r); q = karatsuba_algorithm(q, s); t = karatsuba_algorithm(t, u); vector res(2 * n - 1, 0); for(int i = 0; i < n - 1; ++i){ res[i] += q[i]; res[i + h] += t[i] - p[i] - q[i]; res[i + n] += p[i]; } return res; } pair divide_naive(const BigInt& rhs) const { assert(!rhs.val.empty()); const int k = base / (rhs.val.back() + 1); const BigInt dividend = (sign == 1 ? *this : -(*this)) * k; const BigInt divisor = (rhs.sign == 1 ? rhs : -rhs) * k; BigInt quo, rem = 0; quo.val.resize(dividend.val.size()); const int n = divisor.val.size(); for(int i = (int) dividend.val.size() - 1; i >= 0; --i){ rem.val.emplace(rem.val.begin(), dividend.val[i]); quo.val[i] = ((n < (int) rem.val.size() ? rem.val[n] * base : 0) + ((n - 1) < (int) rem.val.size() ? rem.val[n - 1] : 0)) / divisor.val.back(); rem -= divisor * quo.val[i]; while (rem.sign == -1) { rem += divisor; --quo.val[i]; } } quo.sign = sign * rhs.sign; quo.normalize(); rem.sign = sign; rem.normalize(); return {quo, rem / k}; } pair divide_newton(const BigInt& rhs) const { assert(!rhs.val.empty()); int preci = val.size() - rhs.val.size(); BigInt t(1); BigInt two = BigInt(2) << rhs.val.size(); BigInt pre; int lim = min(preci, 3); int rhslim = min(int(rhs.val.size()), 6); t <<= lim; while(pre != t){ BigInt rb = rhs >> (rhs.val.size() - rhslim); if(rhslim != (int) rhs.val.size()) rb += BigInt(1); pre = t; t *= (BigInt(2) << (rhslim + lim)) - rb * t; t.val = vector(t.val.begin() + lim + rhslim, t.val.end()); } if(lim != preci){ pre = BigInt(); while(pre != t){ BigInt rb = rhs >> (rhs.val.size() - rhslim); if(rhslim != (int) rhs.val.size()) rb += BigInt(1); pre = t; t *= (BigInt(2) << (rhslim + lim)) - rb * t; t.val = vector(t.val.begin() + lim + rhslim, t.val.end()); int next_lim = min(lim * 2 + 1, preci); if (next_lim != lim) t <<= next_lim - lim; int next_rhslim = min(rhslim * 2 + 1, int(rhs.val.size())); lim = next_lim; rhslim = next_rhslim; } } BigInt quo = (*this) * t; quo.val = vector(quo.val.begin() + val.size(), quo.val.end()); BigInt mul = quo * rhs; while(mul + rhs <= (*this)){ quo += BigInt(1); mul += rhs; } BigInt rem = *this - quo * rhs; return {quo, rem}; } public: void stoi(string &s){ if(s == "0") return; int n = s.size(), idx = 0; if(s[0] == '-'){ n -= 1; sign = -1; idx = 1; } int len = (n + digit - 1) / digit, rem = n % digit; if(rem == 0) rem += digit; val.resize(len); for(int i = len - 1; i >= 0; --i){ if(i == len - 1){ val[i] = stoll(s.substr(idx, rem)); idx += rem; }else{ val[i] = stoll(s.substr(idx, digit)); idx += digit; } } } string itos() const { string res = ""; if(sign == -1) res += "-"; bool flag = false; for(int i = (int) val.size() - 1; i >= 0; --i){ if(val[i] > 0 && !flag){ res += to_string(val[i]); flag = true; }else if(flag){ string rem = to_string(val[i]); res += string(digit - rem.size(), '0') + rem; } } return (res.empty() || res == "-") ? "0" : res; } pair divide_mod(const BigInt& rhs){ assert(!rhs.val.empty()); BigInt div = *this / rhs; return make_pair(div, *this - div * rhs); } BigInt& shift(){ for(int i = 0; i < (int) val.size() - 1; ++i){ if(val[i] >= 0){ val[i + 1] += val[i] / base; val[i] %= base; }else{ long long x = (-val[i] + base - 1) / base; val[i] += x * base; val[i + 1] -= x; } } while(val.back() >= base){ val.emplace_back(val.back() / base); val[val.size() - 2] %= base; } return *this; } BigInt& operator=(const BigInt& x) = default; inline BigInt& operator+=(const BigInt& rhs) noexcept { if(rhs.val.empty()) return *this; if(sign != rhs.sign) return *this -= -rhs; if(val.size() < rhs.val.size()){ val.resize(rhs.val.size()); } for(int i = 0; i < (int) rhs.val.size(); ++i){ val[i] += rhs.val[i]; } return (*this).shift(); } inline BigInt& operator-=(const BigInt& rhs) noexcept { if(rhs.val.empty()) return *this; if(sign != rhs.sign) return *this += -rhs; if((sign == 1 ? *this : -(*this)) < (rhs.sign == 1 ? rhs : -rhs)){ return *this = -(rhs - *this); } for(int i = 0; i < (int) rhs.val.size(); ++i){ val[i] -= rhs.val[i]; } shift(); normalize(); return *this; } // Karatsuba Algorithm (O(N^(1.58))) inline BigInt& operator*=(const BigInt& rhs) noexcept { if(val.empty() || rhs.val.empty()){ return *this = BigInt(); } sign *= rhs.sign; vector rhsval = rhs.val; int k = 1; while(k < (int) max(val.size(), rhsval.size())){ k *= 2; } val.resize(k), rhsval.resize(k); val = karatsuba_algorithm(val, rhsval); shift(); normalize(); return *this; } // Newton method inline BigInt& operator/=(const BigInt& rhst) noexcept { assert(!rhst.val.empty()); if(val.empty()) return *this; if((int) val.size() <= 32 && (int) rhst.val.size() <= 32){ return *this = divide_naive(rhst).first; } BigInt rhs = rhst; int mulsign = sign * rhs.sign; sign = 1, rhs.sign = 1; if(*this < rhs){ return *this = BigInt(); } *this = divide_newton(rhs).first; sign = mulsign; normalize(); return *this; } inline BigInt& operator%=(const BigInt& rhs) noexcept { assert(!rhs.val.empty()); return *this = *this - (*this / rhs) * rhs; } inline BigInt& operator++() { return *this += 1; } inline BigInt operator++(int) { const BigInt res = *this; ++(*this); return res; } inline BigInt& operator--() { return *this -= 1; } inline BigInt operator--(int) { const BigInt res = *this; --(*this); return res; } inline BigInt operator+() const { return *this; } inline BigInt operator-() const { BigInt res = *this; if (!res.val.empty()) res.sign = -res.sign; return res; } inline BigInt& operator<<=(const unsigned int rhs){ if(val.back() >= 1 || (int) val.size() >= 2){ vector tmp(rhs, 0); val.insert(val.begin(), tmp.begin(), tmp.end()); } return *this; } inline BigInt& operator>>=(const unsigned int rhs){ if(rhs == 0) return *this; if(rhs > val.size()) val = {0}; else val = vector(val.begin() + rhs, val.end()); return *this; } inline bool operator<(const BigInt& rhs) const { if(sign != rhs.sign) return sign < rhs.sign; if(val.size() != rhs.val.size()) return sign * val.size() < rhs.sign * rhs.val.size(); for(int i = (int) val.size() - 1; i >= 0; --i){ if(val[i] != rhs.val[i]) return sign * val[i] < rhs.sign * rhs.val[i]; } return false; } inline bool operator>(const BigInt& rhs) const { return rhs < (*this); } inline bool operator<=(const BigInt& rhs) const { return !((*this) > rhs); } inline bool operator>=(const BigInt& rhs) const { return !((*this) < rhs); } friend inline BigInt operator+(const BigInt& lhs, const BigInt& rhs) noexcept { return BigInt(lhs) += rhs; } friend inline BigInt operator-(const BigInt& lhs, const BigInt& rhs) noexcept { return BigInt(lhs) -= rhs; } friend inline BigInt operator*(const BigInt& lhs, const BigInt& rhs) noexcept { return BigInt(lhs) *= rhs; } friend inline BigInt operator/(const BigInt& lhs, const BigInt& rhs) noexcept { return BigInt(lhs) /= rhs; } friend inline BigInt operator%(const BigInt& lhs, const BigInt& rhs) noexcept { return BigInt(lhs) %= rhs; } friend inline BigInt operator<<(const BigInt& lhs, const unsigned int rhs) noexcept { return BigInt(lhs) <<= rhs; } friend inline BigInt operator>>(const BigInt& lhs, const unsigned int rhs) noexcept { return BigInt(lhs) >>= rhs; } friend inline bool operator==(const BigInt& lhs, const BigInt& rhs) noexcept { return lhs.val == rhs.val; } friend inline bool operator!=(const BigInt& lhs, const BigInt& rhs) noexcept { return lhs.val != rhs.val; } friend inline istream& operator>>(istream& is, BigInt& x) noexcept { string s; is >> s; x.stoi(s); return is; } friend inline ostream& operator<<(ostream& os, const BigInt& x) noexcept { return os << x.itos(); } }; using bint = BigInt<1000000LL, 6>; struct fraction{ bint p, q; fraction(bint P = 0, bint Q = 1): p(P), q(Q){ } inline bool operator==(const fraction &other) const { return p * other.q == other.p * q; } inline bool operator!=(const fraction &other) const { return p * other.q != other.p * q; } inline bool operator<(const fraction &other) const { return p * other.q < other.p * q; } inline bool operator<=(const fraction &other) const { return p * other.q <= other.p * q; } inline bool operator>(const fraction &other) const { return p * other.q > other.p * q; } inline bool operator>=(const fraction &other) const { return p * other.q >= other.p * q; } inline fraction operator+(const fraction &other) const { return fraction(p * other.q + q * other.p, q * other.q); } inline fraction operator-(const fraction &other) const { return fraction(p * other.q - q * other.p, q * other.q); } inline fraction operator*(const fraction &other) const { return fraction(p * other.p, q * other.q); } inline fraction operator/(const fraction &other) const { return fraction(p * other.q, q * other.p); } inline fraction& operator+=(const fraction& rhs) noexcept { *this = *this + rhs; return *this; } inline fraction& operator-=(const fraction& rhs) noexcept { *this = *this - rhs; return *this; } inline fraction& operator*=(const fraction& rhs) noexcept { *this = *this * rhs; return *this; } inline fraction& operator/=(const fraction& rhs) noexcept { *this = *this / rhs; return *this; } friend inline istream& operator>>(istream& is, fraction& x) noexcept { is >> x.p; x.q = 1; return is; } friend inline ostream& operator<<(ostream& os, const fraction& x) noexcept { return os << x.p << "/" << x.q; } }; void input(){ } using Point = pair; fraction dist(Point p, Point q){ return (p.first - q.first) * (p.first - q.first) + (p.second - q.second) * (p.second - q.second); } void solve(){ ll q; bint x1, y1, x2, y2, x3, y3; in(q); in(x1, y1, x2, y2, x3, y3); vector> xy(3); xy[0] = {x1, y1}, xy[1] = {x2, y2}, xy[2] = {x3, y3}; Sort(xy); Point p; if((x1 - x2) * (y1 - y3) - (x1 - x3) * (y1 - y2) == 0){ fraction x_p(xy[0].first + xy[2].first, 2); fraction y_p(xy[0].second + xy[2].second, 2); p = {x_p, y_p}; }else{ fraction x_p((y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) - (y1 - y3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1), 2 * (x1 - x2) * (y1 - y3) - 2 * (x1 - x3) * (y1 - y2)); fraction y_p((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1) - (x1 - x2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1), 2 * (x1 - x2) * (y1 - y3) - 2 * (x1 - x3) * (y1 - y2)); p = {x_p, y_p}; } Point a = {fraction(x1, 1), fraction(y1, 1)}, b = {fraction(x2, 1), fraction(y2, 1)}, c = {fraction(x3, 1), fraction(y3, 1)}; fraction r = dist(p, a); chmax(r, dist(p, b)); chmax(r, dist(p, c)); while(q--){ fraction x, y; in(x, y); Point q = {x, y}; if(dist(p, q) <= r){ out("Yes"); }else{ out("No"); } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20); input(); solve(); }