/* #region Head */ // #include #include #include #include #include // assert.h #include // math.h #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pll = pair; template using vc = vector; template using vvc = vc>; using vll = vc; using vvll = vvc; using vld = vc; using vvld = vvc; using vs = vc; using vvs = vvc; template using um = unordered_map; template using pq = priority_queue; template using pqa = priority_queue, greater>; template using us = unordered_set; #define TREP(T, i, m, n) for (T i = (m), i##_len = (T)(n); i < i##_len; ++(i)) #define TREPM(T, i, m, n) for (T i = (m), i##_max = (T)(n); i <= i##_max; ++(i)) #define TREPR(T, i, m, n) for (T i = (m), i##_min = (T)(n); i >= i##_min; --(i)) #define TREPD(T, i, m, n, d) for (T i = (m), i##_len = (T)(n); i < i##_len; i += (d)) #define TREPMD(T, i, m, n, d) for (T i = (m), i##_max = (T)(n); i <= i##_max; i += (d)) #define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i)) #define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i)) #define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i)) #define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d)) #define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d)) #define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) #define REPIR(itr, ds) for (auto itr = ds.rbegin(); itr != ds.rend(); itr++) #define ALL(x) begin(x), end(x) #define SIZE(x) ((ll)(x).size()) #define ISIZE(x) ((int)(x).size()) #define PERM(c) \ sort(ALL(c)); \ for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c))) #define UNIQ(v) v.erase(unique(ALL(v)), v.end()); #define CEIL(a, b) (((a) + (b)-1) / (b)) #define endl '\n' constexpr ll INF = 1'010'000'000'000'000'017LL; constexpr int IINF = 1'000'000'007LL; constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7 // constexpr ll MOD = 998244353; constexpr ld EPS = 1e-12; constexpr ld PI = 3.14159265358979323846; template istream &operator>>(istream &is, vc &vec) { // vector 入力 for (T &x : vec) is >> x; return is; } template ostream &operator<<(ostream &os, const vc &vec) { // vector 出力 (for dump) os << "{"; REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", "); os << "}"; return os; } template ostream &operator>>(ostream &os, const vc &vec) { // vector 出力 (inline) REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " "); return os; } template istream &operator>>(istream &is, array &arr) { // array 入力 REP(i, 0, SIZE(arr)) is >> arr[i]; return is; } template ostream &operator<<(ostream &os, const array &arr) { // array 出力 (for dump) os << "{"; REP(i, 0, SIZE(arr)) os << arr[i] << (i == i_len - 1 ? "" : ", "); os << "}"; return os; } template istream &operator>>(istream &is, pair &pair_var) { // pair 入力 is >> pair_var.first >> pair_var.second; return is; } template ostream &operator<<(ostream &os, const pair &pair_var) { // pair 出力 os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // map, um, set, us 出力 template ostream &out_iter(ostream &os, const T &map_var) { os << "{"; REPI(itr, map_var) { os << *itr; auto itrcp = itr; if (++itrcp != map_var.end()) os << ", "; } return os << "}"; } template ostream &operator<<(ostream &os, const map &map_var) { return out_iter(os, map_var); } template ostream &operator<<(ostream &os, const um &map_var) { os << "{"; REPI(itr, map_var) { auto [key, value] = *itr; os << "(" << key << ", " << value << ")"; auto itrcp = itr; if (++itrcp != map_var.end()) os << ", "; } os << "}"; return os; } template ostream &operator<<(ostream &os, const set &set_var) { return out_iter(os, set_var); } template ostream &operator<<(ostream &os, const us &set_var) { return out_iter(os, set_var); } template ostream &operator<<(ostream &os, const pq &pq_var) { pq pq_cp(pq_var); os << "{"; if (!pq_cp.empty()) { os << pq_cp.top(), pq_cp.pop(); while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop(); } return os << "}"; } // tuple 出力 template ostream &operator<<(ostream &os, tuple &a) { if constexpr (N < std::tuple_size_v>) { os << get(a); if constexpr (N + 1 < std::tuple_size_v>) { os << ' '; } else if constexpr (end_line) { os << '\n'; } return operator<< (os, a); } return os; } template void print_tuple(tuple &a) { operator<< <0, true>(std::cout, a); } void pprint() { std::cout << endl; } template void pprint(Head &&head, Tail &&...tail) { std::cout << head; if (sizeof...(Tail) > 0) std::cout << ' '; pprint(move(tail)...); } // dump #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head &&head, Tail &&...tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) DUMPOUT << ", "; dump_func(move(tail)...); } // chmax (更新「される」かもしれない値が前) template > bool chmax(T &xmax, const U &x, Comp comp = {}) { if (comp(xmax, x)) { xmax = x; return true; } return false; } // chmin (更新「される」かもしれない値が前) template > bool chmin(T &xmin, const U &x, Comp comp = {}) { if (comp(x, xmin)) { xmin = x; return true; } return false; } // ローカル用 #ifndef ONLINE_JUDGE #define DEBUG_ #endif #ifndef MYLOCAL #undef DEBUG_ #endif #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif #define VAR(type, ...) \ type __VA_ARGS__; \ assert((std::cin >> __VA_ARGS__)); template istream &operator,(istream &is, T &rhs) { return is >> rhs; } template ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; } struct AtCoderInitialize { static constexpr int IOS_PREC = 15; static constexpr bool AUTOFLUSH = false; AtCoderInitialize() { ios_base::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr); std::cout << fixed << setprecision(IOS_PREC); if (AUTOFLUSH) std::cout << unitbuf; } } ATCODER_INITIALIZE; void Yn(bool p) { std::cout << (p ? "Yes" : "No") << endl; } void YN(bool p) { std::cout << (p ? "YES" : "NO") << endl; } template constexpr void operator--(vc &v, int) noexcept { for (int i = 0; i < ISIZE(v); ++i) v[i]--; } template constexpr void operator++(vc &v, int) noexcept { for (int i = 0; i < ISIZE(v); ++i) v[i]++; } /* #endregion */ // #include // using namespace atcoder; /* #region __int128_t */ // output std::ostream &operator<<(std::ostream &dest, const __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } const int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } // string to __int128_t __int128_t parse(const string &s) { __int128_t ret = 0; for (int i = 0; i < (int)s.length(); ++i) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } template void hash_combine(size_t &seed, T const &v) { // 基本型に関するハッシュ生成は標準ライブラリが提供している std::hash primitive_type_hash; // 生成したハッシュを合成する。このコードはboostものを使用する seed ^= primitive_type_hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } // template <> struct std::hash<__int128_t> { // public: // // クラスのメンバの値それぞれについてハッシュ生成して、それらを結合して一つのハッシュ値にする // size_t operator()(const __int128_t &data) const { // std::size_t seed = 0; // hash_combine(seed, (unsigned long long)data); // hash_combine(seed, (unsigned long long)(data >> 64)); // return seed; // } // }; /* #endregion */ /* #region Rational */ template struct RationalNum { // 分子 T numerator; // 分母 T denominator; RationalNum() { numerator = 0, denominator = 1; } // RationalNum(double x); RationalNum(T numerator_, T denominator_ = 1) { numerator = numerator_, denominator = denominator_; simplify(); } // 自身を簡約する void simplify() { RationalNum::simplifyNums(numerator, denominator); } static T mygcd(const T &a, const T &b) { // std::gcd が使える場合 if constexpr ((std::is_integral::value)) { return std::gcd(a, b); } // std::gcd が使えない場合 (__int128_t など) if (b == 0) { return a; } else { return mygcd(b, a % b); } } static void simplifyNums(T &numerator_, T &denominator_) { if (denominator_ == 0) { // 分母が 0 のときの正規化 if (numerator_ > 0) numerator_ = 1; // 無限大 else if (numerator_ < 0) numerator_ = -1; // 無限小 else numerator_ = 0; // 不定 } else { T g = mygcd(numerator_, denominator_); numerator_ /= g, denominator_ /= g; if (denominator_ < 0) numerator_ *= -1, denominator_ *= -1; } } // 逆数を返す. RationalNum inv() const { return RationalNum(denominator, numerator); } // t 乗を返す. RationalNum pow(ll t) const { RationalNum a(*this); RationalNum res = 1; while (t) { if (t & 1) res *= a; t >>= 1, a *= a; } return res; } // 小数点以下を切り上げた整数を返す T ceil() const { if (numerator >= 0) return (numerator + denominator - 1) / denominator; else return numerator / denominator; } // 小数点以下を切り捨てた整数を返す T floor() const { if (numerator >= 0) return numerator / denominator; else return (numerator - denominator + 1) / denominator; } // operator ll() const { return floor(); } // member function RationalNum &operator+=(const RationalNum &obj) { return *this = *this + obj; } RationalNum &operator-=(const RationalNum &obj) { return *this = *this - obj; } RationalNum &operator*=(const RationalNum &obj) { return *this = *this * obj; } RationalNum &operator/=(const RationalNum &obj) { return *this = *this / obj; } RationalNum &operator++() { return *this = *this + 1; } RationalNum operator++(int) { RationalNum before = *this; *this = *this + 1; return before; } RationalNum &operator--() { return *this = *this - 1; } RationalNum operator--(int) { RationalNum before = *this; *this = *this - 1; return before; } RationalNum operator+() const { return *this; } RationalNum operator-() const { return RationalNum(-numerator, denominator); } // friend functions friend RationalNum operator+(const RationalNum &left, const RationalNum &right) { if (left.denominator == 0 && right.denominator == 0) { if (left.numerator == 0) return left; // left が不定 if (right.numerator == 0) return right; // right が不定 if ((left > 0 && right > 0) || (left < 0 && right < 0)) { return left; // 無限大・無限小 } else { return RationalNum(0, 0); // 不定 } } else if (left.denominator == 0) { return left; } else if (right.denominator == 0) { return right; } RationalNum temp; T tempLD = left.denominator; T tempRD = right.denominator; RationalNum::simplifyNums(tempLD, tempRD); temp.denominator = left.denominator * tempRD; temp.numerator = left.numerator * tempRD + right.numerator * tempLD; temp.simplify(); return temp; } friend RationalNum operator-(const RationalNum &left, const RationalNum &right) { return left + (-right); // } friend RationalNum operator*(const RationalNum &left, const RationalNum &right) { T a = left.denominator, b = right.numerator, c = right.denominator, d = left.numerator; RationalNum::simplifyNums(b, a), RationalNum::simplifyNums(d, c); return RationalNum(b * d, a * c); } friend RationalNum operator/(const RationalNum &left, const RationalNum &right) { return left * right.inv(); // } friend bool operator==(const RationalNum &left, const RationalNum &right) { return (left.numerator == right.numerator && left.denominator == right.denominator); } friend bool operator!=(const RationalNum &left, const RationalNum &right) { return !(left == right); // } friend bool operator<(const RationalNum &left, const RationalNum &right) { RationalNum indeterminate(0, 0); if (left == indeterminate || right == indeterminate) { // どちらかが不定のときは大小を正しく計算できないので,特別扱いする // 便宜上,不定は「無限大より大きい」として扱う if (right != indeterminate) { return false; } else if (left != indeterminate) { return true; } else { return false; } } if constexpr ((std::is_integral::value)) { ll lside; bool of0 = __builtin_mul_overflow(left.numerator, right.denominator, &lside); // = left.numerator * right.denominator; ll rside; bool of1 = __builtin_mul_overflow(left.denominator, right.numerator, &rside); // left.denominator * right.numerator; if (!of0 && !of1) return (lside < rside); // 両方ok } __int128_t lside128 = __int128_t(left.numerator) * right.denominator; __int128_t rside128 = __int128_t(left.denominator) * right.numerator; return (lside128 < rside128); } // // 積が ll を超えることもあるので,map のキーで使うとかのときは, // // 異なる RationalNum の間に必ず大小関係が定義できる(ただし分数の大小とは異なる)こちらを使う? // friend bool operator<(const RationalNum &left, const RationalNum &right) { // return left.numerator == right.numerator ? left.denominator < right.denominator : left.numerator < // right.numerator; // } friend bool operator>(const RationalNum &left, const RationalNum &right) { // ll lside = left.getNumerator() * right.getDenominator(); // ll rside = left.getDenominator() * right.getNumerator(); // return (lside > rside); return !(left < right) && (left != right); } friend bool operator<=(const RationalNum &left, const RationalNum &right) { return ((left < right) || (left == right)); } friend bool operator>=(const RationalNum &left, const RationalNum &right) { return ((left > right) || (left == right)); } // 出力 friend ostream &operator<<(ostream &out, const RationalNum &obj) { if (obj.denominator == 0) { if (obj.numerator > 0) out << "inf"; else if (obj.numerator < 0) out << "-inf"; else out << "indeterminate"; } else { out << obj.numerator; if (obj.numerator != 0 && obj.denominator != 1) out << "/" << obj.denominator; } return out; } // 小数の入力には使っても問題なさそう // https://atcoder.jp/contests/abc169/tasks/abc169_c // 入力 friend istream &operator>>(istream &in, RationalNum &obj) { string inputstr; T num = 0; int sign = 1; bool slashExist = false; bool dotExist = false; // bool validInput = true; T virtualDenominator = 1; cin >> inputstr; REP(i, 0, SIZE(inputstr)) { char temp = inputstr[i]; if (temp == '.') { if (dotExist == false && slashExist == false && i != 0) { dotExist = true; } // else { // validInput = false; // break; // } } else if (temp == '/') { if (dotExist == false && slashExist == false && i != 0) { slashExist = true; obj.numerator = (sign * num); num = 0; sign = 1; } // else { // validInput = false; // break; // } } else if (temp == '-') { if (i == 0) { sign = -sign; } else if (inputstr[i - 1] == '/') { sign = -sign; } // else { // validInput = false; // break; // } } else if (temp <= '9' && temp >= '0') { if (dotExist) { // if (virtualDenominator > INF / 10) { // cerr << "this frational is too long to handle."; // validInput = false; // break; // } else virtualDenominator *= 10; } // if (num > INF / 10) { // cerr << "this number is too long to handle."; // validInput = false; // break; // } num *= 10; num += inputstr[i] - '0'; } // else { // validInput = false; // break; // } } // if (validInput == false) { // obj.numerator = (0); // obj.denominator = (1); // cerr << "Input is not valid! The whole set to 0" << endl; // } if (slashExist == true) { obj.denominator = (sign * num); } else if (dotExist) { obj.numerator = (sign * num); obj.denominator = (virtualDenominator); } else { obj.numerator = (sign * num); obj.denominator = (1); } obj.simplify(); return in; } }; // __int128_t を使わない場合はアンコメントする // template void hash_combine(size_t &seed, T const &v) { // // 基本型に関するハッシュ生成は標準ライブラリが提供している // std::hash primitive_type_hash; // // 生成したハッシュを合成する。このコードはboostものを使用する // seed ^= primitive_type_hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); // } template struct std::hash> { public: // クラスのメンバの値それぞれについてハッシュ生成して、それらを結合して一つのハッシュ値にする size_t operator()(const RationalNum &data) const { std::size_t seed = 0; hash_combine(seed, data.numerator); hash_combine(seed, data.denominator); return seed; } }; /* #endregion */ // Problem void solve() { using T = __int128_t; using Rat = RationalNum; VAR(ll, q); // VAR(ll, xa, ya, xb, yb, xc, yc); vc X(3), Y(3); REP(i, 0, 3) cin >> X[i], Y[i]; vc x(q), y(q); REP(i, 0, q) cin >> x[i], y[i]; // dump(X, Y, x, y); // パターンとして,次の2通りのいずれかを判定する // 1. ある2点を結ぶ線分が直径になっている円 // 2. 3点を通る円 ll diameter_idx = -1; REP(i, 0, 3) { // [i]-[i+1] の線分が直径である円は,[i+2] を内部または周上に含むか? Rat cx = (X[i] + X[(i + 1) % 3]) / 2; Rat cy = (Y[i] + Y[(i + 1) % 3]) / 2; // 円の半径^2 Rat r2 = (X[i] - cx).pow(2) + (Y[i] - cy).pow(2); // 中心からの距離^2 Rat d2 = (X[(i + 2) % 3] - cx).pow(2) + (Y[(i + 2) % 3] - cy).pow(2); if (d2 <= r2) { diameter_idx = i; break; } } // dump(diameter_idx); Rat cx, cy, r2; if (diameter_idx == -1) { // 3点を通る円の外心 // https://w3e.kanazawa-it.ac.jp/math/category/kika/heimenkika/henkan-tex.cgi?target=/math/category/kika/heimenkika/gaisinn_motomekata.html // x 座標 const Rat cx_num = (X[0].pow(2) + Y[0].pow(2)) * (Y[1] - Y[2]) + // (X[1].pow(2) + Y[1].pow(2)) * (Y[2] - Y[0]) + // (X[2].pow(2) + Y[2].pow(2)) * (Y[0] - Y[1]); const Rat cx_den = (X[0] - X[1]) * (Y[1] - Y[2]) - // (X[1] - X[2]) * (Y[0] - Y[1]); cx = cx_num / cx_den / 2; // y 座標 const Rat cy_num = (X[0].pow(2) + Y[0].pow(2)) * (X[1] - X[2]) + // (X[1].pow(2) + Y[1].pow(2)) * (X[2] - X[0]) + // (X[2].pow(2) + Y[2].pow(2)) * (X[0] - X[1]); const Rat cy_den = (X[1] - X[2]) * (Y[0] - Y[1]) - // (X[0] - X[1]) * (Y[1] - Y[2]); cy = cy_num / cy_den / 2; // 半径 const Rat dx = cx - X[0]; const Rat dy = cy - Y[0]; r2 = dx.pow(2) + dy.pow(2); // dump(cx, cy, r2); } else { // 2点を結ぶ線分を直径とする円 cx = (X[diameter_idx] + X[(diameter_idx + 1) % 3]) / 2; cy = (Y[diameter_idx] + Y[(diameter_idx + 1) % 3]) / 2; r2 = (X[diameter_idx] - cx).pow(2) + (Y[diameter_idx] - cy).pow(2); // dump(cx, cy, r2); } REP(i, 0, q) { Rat d2 = (x[i] - cx).pow(2) + (y[i] - cy).pow(2); Yn(d2 <= r2); } } // entry point int main() { solve(); return 0; }