結果
| 問題 | No.2602 Real Collider |
| ユーザー |
 iiljj
|
| 提出日時 | 2024-01-27 14:20:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 690 ms / 2,000 ms |
| コード長 | 29,294 bytes |
| コンパイル時間 | 6,196 ms |
| コンパイル使用メモリ | 402,212 KB |
| 実行使用メモリ | 15,616 KB |
| 最終ジャッジ日時 | 2024-09-28 09:38:18 |
| 合計ジャッジ時間 | 28,607 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 3 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 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | AC | 2 ms
5,376 KB |
| testcase_09 | AC | 2 ms
5,376 KB |
| testcase_10 | AC | 690 ms
15,616 KB |
| testcase_11 | AC | 253 ms
7,808 KB |
| testcase_12 | AC | 161 ms
9,088 KB |
| testcase_13 | AC | 74 ms
5,888 KB |
| testcase_14 | AC | 163 ms
9,488 KB |
| testcase_15 | AC | 203 ms
6,528 KB |
| testcase_16 | AC | 308 ms
8,448 KB |
| testcase_17 | AC | 335 ms
9,088 KB |
| testcase_18 | AC | 106 ms
7,424 KB |
| testcase_19 | AC | 135 ms
8,192 KB |
| testcase_20 | AC | 373 ms
9,984 KB |
| testcase_21 | AC | 103 ms
7,040 KB |
| testcase_22 | AC | 127 ms
7,936 KB |
| testcase_23 | AC | 78 ms
6,272 KB |
| testcase_24 | AC | 114 ms
7,680 KB |
| testcase_25 | AC | 118 ms
7,936 KB |
| testcase_26 | AC | 170 ms
6,528 KB |
| testcase_27 | AC | 142 ms
8,576 KB |
| testcase_28 | AC | 278 ms
8,960 KB |
| testcase_29 | AC | 121 ms
7,808 KB |
| testcase_30 | AC | 132 ms
8,192 KB |
| testcase_31 | AC | 349 ms
8,448 KB |
| testcase_32 | AC | 281 ms
7,680 KB |
| testcase_33 | AC | 331 ms
8,448 KB |
| testcase_34 | AC | 293 ms
8,448 KB |
| testcase_35 | AC | 202 ms
6,656 KB |
| testcase_36 | AC | 164 ms
6,656 KB |
| testcase_37 | AC | 364 ms
8,960 KB |
| testcase_38 | AC | 352 ms
9,216 KB |
| testcase_39 | AC | 360 ms
8,960 KB |
| testcase_40 | AC | 166 ms
5,888 KB |
| testcase_41 | AC | 387 ms
9,720 KB |
| testcase_42 | AC | 296 ms
8,192 KB |
| testcase_43 | AC | 274 ms
8,320 KB |
| testcase_44 | AC | 419 ms
9,728 KB |
| testcase_45 | AC | 235 ms
7,424 KB |
| testcase_46 | AC | 238 ms
7,040 KB |
| testcase_47 | AC | 369 ms
9,132 KB |
| testcase_48 | AC | 270 ms
7,552 KB |
| testcase_49 | AC | 253 ms
7,040 KB |
| testcase_50 | AC | 178 ms
6,016 KB |
| testcase_51 | AC | 186 ms
6,400 KB |
| testcase_52 | AC | 132 ms
5,376 KB |
| testcase_53 | AC | 322 ms
8,448 KB |
| testcase_54 | AC | 238 ms
7,296 KB |
| testcase_55 | AC | 264 ms
7,808 KB |
| testcase_56 | AC | 294 ms
7,680 KB |
| testcase_57 | AC | 254 ms
7,424 KB |
| testcase_58 | AC | 90 ms
5,376 KB |
| testcase_59 | AC | 339 ms
8,320 KB |
| testcase_60 | AC | 244 ms
7,936 KB |
| testcase_61 | AC | 209 ms
6,784 KB |
| testcase_62 | AC | 334 ms
8,576 KB |
| testcase_63 | AC | 343 ms
9,344 KB |
| testcase_64 | AC | 432 ms
10,240 KB |
| testcase_65 | AC | 206 ms
6,656 KB |
| testcase_66 | AC | 348 ms
8,960 KB |
| testcase_67 | AC | 143 ms
5,888 KB |
| testcase_68 | AC | 166 ms
6,272 KB |
| testcase_69 | AC | 112 ms
5,376 KB |
| testcase_70 | AC | 141 ms
5,888 KB |
| testcase_71 | AC | 201 ms
6,528 KB |
| testcase_72 | AC | 304 ms
8,424 KB |
| testcase_73 | AC | 242 ms
7,552 KB |
| testcase_74 | AC | 322 ms
8,576 KB |
| testcase_75 | AC | 327 ms
8,960 KB |
| testcase_76 | AC | 291 ms
8,064 KB |
| testcase_77 | AC | 299 ms
8,320 KB |
| testcase_78 | AC | 389 ms
9,600 KB |
| testcase_79 | AC | 297 ms
8,772 KB |
| testcase_80 | AC | 341 ms
9,600 KB |
ソースコード
/* #region Head */
// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert> // assert.h
#include <cmath> // math.h
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;
#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 <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
for (T &x : vec) is >> x;
return is;
}
template <typename T> ostream &operator<<(ostream &os, const vc<T> &vec) { // vector 出力 (for dump)
os << "{";
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T> ostream &operator>>(ostream &os, const vc<T> &vec) { // vector 出力 (inline)
REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
return os;
}
template <typename T, size_t _Nm> istream &operator>>(istream &is, array<T, _Nm> &arr) { // array 入力
REP(i, 0, SIZE(arr)) is >> arr[i];
return is;
}
template <typename T, size_t _Nm> ostream &operator<<(ostream &os, const array<T, _Nm> &arr) { // array 出力 (for dump)
os << "{";
REP(i, 0, SIZE(arr)) os << arr[i] << (i == i_len - 1 ? "" : ", ");
os << "}";
return os;
}
template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
is >> pair_var.first >> pair_var.second;
return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &pair_var) { // pair 出力
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
// map, um, set, us 出力
template <class T> 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 <typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &map_var) {
return out_iter(os, map_var);
}
template <typename T, typename U> ostream &operator<<(ostream &os, const um<T, U> &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 <typename T> ostream &operator<<(ostream &os, const set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, const pq<T> &pq_var) {
pq<T> 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 <size_t N = 0, bool end_line = false, typename... Args> ostream &operator<<(ostream &os, tuple<Args...> &a) {
if constexpr (N < std::tuple_size_v<tuple<Args...>>) {
os << get<N>(a);
if constexpr (N + 1 < std::tuple_size_v<tuple<Args...>>) {
os << ' ';
} else if constexpr (end_line) {
os << '\n';
}
return operator<< <N + 1, end_line>(os, a);
}
return os;
}
template <typename... Args> void print_tuple(tuple<Args...> &a) { operator<< <0, true>(std::cout, a); }
void pprint() { std::cout << endl; }
template <class Head, class... Tail> 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 <class Head, class... Tail> void dump_func(Head &&head, Tail &&...tail) {
DUMPOUT << head;
if (sizeof...(Tail) > 0) DUMPOUT << ", ";
dump_func(move(tail)...);
}
// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
if (comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> 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 <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }
template <typename T> 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 <typename T> constexpr void operator--(vc<T> &v, int) noexcept {
for (int i = 0; i < ISIZE(v); ++i) v[i]--;
}
template <typename T> constexpr void operator++(vc<T> &v, int) noexcept {
for (int i = 0; i < ISIZE(v); ++i) v[i]++;
}
/* #endregion */
// #include <atcoder/all>
// using namespace atcoder;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
/* #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 <typename T> void hash_combine(size_t &seed, T const &v) {
// 基本型に関するハッシュ生成は標準ライブラリが提供している
std::hash<T> 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 <typename T> 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<T>::simplifyNums(numerator, denominator); }
static T mygcd(const T &a, const T &b) {
// std::gcd が使える場合
if constexpr ((std::is_integral<T>::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<T> inv() const { return RationalNum<T>(denominator, numerator); }
// t 乗を返す．
RationalNum<T> pow(ll t) const {
RationalNum<T> a(*this);
RationalNum<T> res = 1;
while (t) {
if (t & 1) res *= a;
t >>= 1;
if (t == 0) break;
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<T> &operator+=(const RationalNum<T> &obj) { return *this = *this + obj; }
RationalNum<T> &operator-=(const RationalNum<T> &obj) { return *this = *this - obj; }
RationalNum<T> &operator*=(const RationalNum<T> &obj) { return *this = *this * obj; }
RationalNum<T> &operator/=(const RationalNum<T> &obj) { return *this = *this / obj; }
RationalNum<T> &operator++() { return *this = *this + 1; }
RationalNum<T> operator++(int) {
RationalNum<T> before = *this;
*this = *this + 1;
return before;
}
RationalNum<T> &operator--() { return *this = *this - 1; }
RationalNum<T> operator--(int) {
RationalNum<T> before = *this;
*this = *this - 1;
return before;
}
RationalNum<T> operator+() const { return *this; }
RationalNum<T> operator-() const { return RationalNum<T>(-numerator, denominator); }
// friend functions
friend RationalNum<T> operator+(const RationalNum<T> &left, const RationalNum<T> &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<T>(0, 0); // 不定
}
} else if (left.denominator == 0) {
return left;
} else if (right.denominator == 0) {
return right;
}
RationalNum<T> temp;
T tempLD = left.denominator;
T tempRD = right.denominator;
RationalNum<T>::simplifyNums(tempLD, tempRD);
temp.denominator = left.denominator * tempRD;
temp.numerator = left.numerator * tempRD + right.numerator * tempLD;
temp.simplify();
return temp;
}
friend RationalNum<T> operator-(const RationalNum<T> &left, const RationalNum<T> &right) {
return left + (-right); //
}
friend RationalNum<T> operator*(const RationalNum<T> &left, const RationalNum<T> &right) {
T a = left.denominator, b = right.numerator, c = right.denominator, d = left.numerator;
RationalNum<T>::simplifyNums(b, a), RationalNum<T>::simplifyNums(d, c);
return RationalNum<T>(b * d, a * c);
}
friend RationalNum<T> operator/(const RationalNum<T> &left, const RationalNum<T> &right) {
return left * right.inv(); //
}
friend bool operator==(const RationalNum<T> &left, const RationalNum<T> &right) {
return (left.numerator == right.numerator && left.denominator == right.denominator);
}
friend bool operator!=(const RationalNum<T> &left, const RationalNum<T> &right) {
return !(left == right); //
}
friend bool operator<(const RationalNum<T> &left, const RationalNum<T> &right) {
RationalNum<T> indeterminate(0, 0);
if (left == indeterminate || right == indeterminate) {
// どちらかが不定のときは大小を正しく計算できないので，特別扱いする
// 便宜上，不定は「無限大より大きい」として扱う
if (right != indeterminate) {
return false;
} else if (left != indeterminate) {
return true;
} else {
return false;
}
}
// 符号が異なるときはすぐ判定できる
if (left.numerator < 0 && right.numerator >= 0) return true;
if (left.numerator <= 0 && right.numerator > 0) return true;
if (left.numerator > 0 && right.numerator <= 0) return false;
if (left.numerator >= 0 && right.numerator < 0) return false;
// 両方 0 の場合
if (left.numerator == 0 && right.numerator == 0) return false;
// 分母が等しい場合
if (left.denominator == right.denominator) {
return left.numerator < right.numerator;
}
// 分子が等しい場合（通分しないで済むなら嬉しいので）（若干高速化できる）
if (left.numerator == right.numerator) {
if (left.numerator > 0) {
// 正の数→分母が大きいほど分数としては小さい
return left.denominator > right.denominator;
} else {
// 負の数→分母が大きいほど分数としても大きい
return left.denominator < right.denominator;
}
}
// 整数に丸めて比較可能ならそうする（若干高速化できる）
if (left.numerator > 0) {
assert(right.numerator > 0);
const T q_left = left.floor();
const T q_right = right.floor();
if (q_left != q_right) {
return q_left < q_right;
}
} else {
assert(left.numerator < 0);
assert(right.numerator < 0);
const T q_left = left.ceil();
const T q_right = right.ceil();
if (q_left != q_right) {
return q_left < q_right;
}
}
// ジャッジサーバでは __int128_t でも is_integral == true になるので，
// この分岐は使わない
// if constexpr ((std::is_integral<T>::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);
// }
RationalNum<T> diff = right - left;
return diff.numerator > 0;
}
// // 積が 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<T> &left, const RationalNum<T> &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<T> &left, const RationalNum<T> &right) {
return ((left < right) || (left == right));
}
friend bool operator>=(const RationalNum<T> &left, const RationalNum<T> &right) {
return ((left > right) || (left == right));
}
// 出力
friend ostream &operator<<(ostream &out, const RationalNum<T> &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<T> &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 <typename T> void hash_combine(size_t &seed, T const &v) {
// // 基本型に関するハッシュ生成は標準ライブラリが提供している
// std::hash<T> primitive_type_hash;
// // 生成したハッシュを合成する。このコードはboostものを使用する
// seed ^= primitive_type_hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// }
template <typename T> struct std::hash<RationalNum<T>> {
public:
// クラスのメンバの値それぞれについてハッシュ生成して、それらを結合して一つのハッシュ値にする
size_t operator()(const RationalNum<T> &data) const {
std::size_t seed = 0;
hash_combine(seed, data.numerator);
hash_combine(seed, data.denominator);
return seed;
}
};
/* #endregion */
template <typename T> RationalNum<T> testpow(RationalNum<T> a, ll t) {
RationalNum<T> res = 1;
while (t) {
dump(t, t & 1);
if (t & 1) res *= a;
t >>= 1;
if (t == 0) break;
a *= a;
}
return res;
}
int mybitlen(__int128_t v) {
int ret = 0;
while (v != 0) {
v >>= 1;
++ret;
}
return ret;
}
template <typename T> bool testoperator(const RationalNum<T> &left, const RationalNum<T> &right) {
RationalNum<T> 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<T>::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
}
dump(111, mybitlen(left.numerator), mybitlen(right.denominator));
__int128_t lside128 = __int128_t(left.numerator) * right.denominator;
dump(222);
__int128_t rside128 = __int128_t(left.denominator) * right.numerator;
dump(333);
return (lside128 < rside128);
}
// Problem
void solve() {
// using mi = mp::cpp_int;
// using T = mi;
using T = __int128_t;
using Rat = RationalNum<T>;
VAR(ll, q);
// VAR(ll, xa, ya, xb, yb, xc, yc);
// dump(q);
vc<Rat> X(3), Y(3);
REP(i, 0, 3) cin >> X[i], Y[i];
vc<Rat> x(q), y(q);
REP(i, 0, q) cin >> x[i], y[i];
// dump(X, Y, x, y);
// dump(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;
// dump(cx);
// 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;
// dump(cy);
// 半径
const Rat dx = cx - X[0];
const Rat dy = cy - Y[0];
// dump(dx, dy);
// dump(testpow(dx, 2));
// dump(testpow(dy, 2));
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) {
// dump(i);
// dump(x[i] - cx);
// dump(y[i] - cy);
// dump((x[i] - cx).pow(2));
// dump((y[i] - cy).pow(2));
Rat d2 = (x[i] - cx).pow(2) + (y[i] - cy).pow(2);
// dump(d2, r2);
// dump(d2 - r2);
// dump(testoperator(d2, r2));
Yn(d2 <= r2);
}
}
// entry point
int main() {
solve();
return 0;
}