結果
| 問題 | No.2602 Real Collider |
| ユーザー |
 marc2825
|
| 提出日時 | 2024-01-12 22:20:35 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 25,781 bytes |
| コンパイル時間 | 11,064 ms |
| コンパイル使用メモリ | 464,344 KB |
| 実行使用メモリ | 13,480 KB |
| 最終ジャッジ日時 | 2024-01-12 22:20:50 |
| 合計ジャッジ時間 | 13,557 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,480 KB |
| testcase_01 | AC | 2 ms
6,676 KB |
| testcase_02 | AC | 2 ms
6,676 KB |
| testcase_03 | AC | 3 ms
6,676 KB |
| testcase_04 | AC | 2 ms
6,676 KB |
| testcase_05 | AC | 2 ms
6,676 KB |
| testcase_06 | AC | 2 ms
6,676 KB |
| testcase_07 | AC | 2 ms
6,676 KB |
| testcase_08 | AC | 2 ms
6,676 KB |
| testcase_09 | AC | 2 ms
6,676 KB |
| testcase_10 | TLE | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
ソースコード
// #pragma GCC target ("avx")
// #pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#ifdef MARC_LOCAL
#define _GLIBCXX_DEBUG
#endif
#ifdef ATCODER
#include <atcoder/all>
using namespace atcoder;
#endif
#include <bits/stdc++.h>
using namespace std;
//#define int long long
using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vvvvll = vector<vvvll>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using ld = long double; using vld = vector<ld>; using vvld = vector<vld>; using vd = vector<double>;
using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using pii = pair<int, int>; using pcc = pair<char, char>; using pll = pair<ll, ll>; using pli = pair<ll, int>; using pdd = pair<double, double>; using pldld = pair<ld,ld>;
using vpii = vector<pii>; using vvpii = vector<vpii>; using vpll = vector<pll>; using vvpll = vector<vpll>; using vpldld = vector<pldld>;
using ui = unsigned int; using ull = unsigned long long;
using i128 = __int128; using f128 = __float128;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
// #define vv(type, name, h, ...) vector<vector<type> > name(h, vector<type>(__VA_ARGS__))
// #define vvv(type, name, h, w, ...) vector<vector<vector<type> > > name(h, vector<vector<type> >(w, vector<type>(__VA_ARGS__)))
// #define vvvv(type, name, a, b, c, ...) vector<vector<vector<vector<type> > > > name(a, vector<vector<vector<type> > >(b, vector<vector<type> >(c, vector<type>(__VA_ARGS__))))
#define overload4(a,b,c,d,name,...) name
#define rep1(n) for(ll i = 0; i < (ll)n; i++)
#define rep2(i,n) for(ll i = 0; i < (ll)n; i++)
#define rep3(i,a,b) for (ll i = a; i < (ll)b; i++)
#define rep4(i,a,b,c) for (ll i = a; i < (ll)b; i += (ll)c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define repback1(n) for (ll i = (ll)n-1; i >= 0; i--)
#define repback2(i,n) for (ll i = (ll)n-1; i >= 0; i--)
#define repback3(i,a,b) for (ll i = (ll)b-1; i >= (ll)a; i--)
#define repback4(i,a,b,c) for (ll i = (ll)b-1; i >= (ll)a; i -= (ll)c)
#define repback(...) overload4(__VA_ARGS__,repback4,repback3,repback2,repback1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define include(y, x, H, W) (0 <= (y) && (y) < (H) && 0 <= (x) && (x) < (W))
#define inrange(x, down, up) ((down) <= (x) && (x) <= (up))
#define square(x) (x) * (x)
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second
#define equals(a,b) (fabs((a) - (b)) < EPS)
#define TIMER_START TIME_START = clock()
#ifdef MARC_LOCAL
// https://trap.jp/post/1224/
#define debug1(x) cout << "debug: " << (#x) << ": " << (x) << endl
#define debug2(x, y) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << endl
#define debug3(x, y, z) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << endl
#define debug4(x, y, z, w) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << ", " << (#w) << ": " << (w) << endl
#define debug5(x, y, z, w, v) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << ", " << (#w) << ": " << (w) << ", " << (#v) << ": " << (v) << endl
#define debug6(x, y, z, w, v, u) cout << "debug: " << (#x) << ": " << (x) << ", " << (#y) << ": " << (y) << ", " << (#z) << ": " << (z) << ", " << (#w) << ": " << (w) << ", " << (#v) << ": " << (v) << ", " << (#u) << ": " << (u) << endl
#define overload6(a, b, c, d, e, f, g,...) g
#define debug(...) overload6(__VA_ARGS__, debug6, debug5, debug4, debug3, debug2, debug1)(__VA_ARGS__)
#define debuga cerr << "a" << endl
#define debugnl cout << endl
#define Case(i) cout << "Case #" << (i) << ": "
#define TIMECHECK cerr << 1000.0 * static_cast<double>(clock() - TIME_START) / CLOCKS_PER_SEC << "ms" << endl
#define LOCAL 1
#else
#define debug1(x) void(0)
#define debug2(x, y) void(0)
#define debug3(x, y, z) void(0)
#define debug4(x, y, z, w) void(0)
#define debug5(x, y, z, w, v) void(0)
#define debug6(x, y, z, w, v, u) void(0)
#define debug(...) void(0)
#define debuga void(0)
#define debugnl void(0)
#define Case(i) void(0)
#define TIMECHECK void(0)
#define LOCAL 0
#endif
//mt19937_64 rng(0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
clock_t TIME_START;
const long double pi = 3.1415926535897932;
const long long INFL = 1000000000000000000ll;
const long long INFLMAX = numeric_limits< long long >::max(); // 9223372036854775807
const int INF = 1000000000;
const int INFMAX = numeric_limits< int >::max(); // 2147483647
const long double INFD = numeric_limits<ld>::infinity();
const long double EPS = 1e-9;
const int mod1 = 1000000007;
const int mod2 = 998244353;
const vi dx1 = {1,0,-1,0};
const vi dy1 = {0,1,0,-1};
const vi dx2 = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const vi dy2 = {1, 1, 0, -1, -1, -1, 0, 1, 1};
constexpr char nl = '\n';
constexpr char bl = ' ';
std::ostream &operator<<(std::ostream &dest, __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 = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest; }
__int128 parse(string &s) { __int128 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; } // for __int128 (https://kenkoooo.hatenablog.com/entry/2016/11/30/163533)
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) { os << "["; for (int i = 0; i<(int)vec.size(); i++) { os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", "); } os << "]"; return os; } /// vector 出力
template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // pair 出力
template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) { os << "{"; for (auto itr = map_var.begin(); itr != map_var.end(); itr++) { os << "(" << itr->first << ", " << itr->second << ")"; itr++; if(itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // map出力
template<typename T> ostream& operator << (ostream& os, set<T>& set_var) { os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } /// set 出力
int popcnt(unsigned long long a){ return __builtin_popcountll(a); } // ll は 64bit対応！
int MSB1(unsigned long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } // MSB(1), 0-indexed ( (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) )
int LSB1(unsigned long long x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } // LSB(1), 0-indexed ( (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2) )
long long pow2(int n) { return 1LL << n; }
long long maskbit(int n) { return (1LL << n) - 1; }
bool bit_is1(long long x, int i) { return ((x>>i) & 1); }
string charrep(int n, char c) { return std::string(n, c); }
template<class T>void UNIQUE(T& A) {sort(all(A)); A.erase(unique(all(A)), A.end());}
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T, class U> bool chmin(T& a, const U& b){ return chmin(a, (T)b); }
template<class T, class U> bool chmax(T& a, const U& b){ return chmax(a, (T)b); }
void YESNO(bool b) {if(b){cout<<"YES"<<'\n';} else{cout<<"NO"<<'\n';}} void YES() {YESNO(true);} void NO() {YESNO(false);}
void yesno(bool b) {if(b){cout<<"yes"<<'\n';} else{cout<<"no"<<'\n';}} void yes() {yesno(true);} void no() {yesno(false);}
void POSIMPOS(bool b) {if(b){cout<<"POSSIBLE"<<'\n';} else{cout<<"IMPOSSIBLE"<<'\n';}}
void PosImpos(bool b) {if(b){cout<<"Possible"<<'\n';} else{cout<<"Impossible"<<'\n';}}
void posimpos(bool b) {if(b){cout<<"possible"<<'\n';} else{cout<<"impossible"<<'\n';}}
void FIRSEC(bool b) {if(b){cout<<"FIRST"<<'\n';} else{cout<<"SECOND"<<'\n';}}
void firsec(bool b) {if(b){cout<<"first"<<'\n';} else{cout<<"second"<<'\n';}}
void FirSec(bool b) {if(b){cout<<"First"<<'\n';} else{cout<<"Second"<<'\n';}}
void AliBob(bool b) {if(b){cout<<"Alice"<<'\n';} else{cout<<"Bob"<<'\n';}}
void TakAok(bool b) {if(b){cout<<"Takahashi"<<'\n';} else{cout<<"Aoki"<<'\n';}}
int GetTime() {return 1000.0*static_cast<double>(clock() - TIME_START) / CLOCKS_PER_SEC;}
ll myRand(ll B) {return (unsigned long long)rng() % B;}
template<typename T> void print(const T& x, const char endch = '\n') { cout << x << endch; }
template<class T> T ceil_div(T x, T y) { assert(y); return (x > 0 ? (x + y - 1) / y : x / y); }
template<class T> T floor_div(T x, T y) { assert(y); return (x > 0 ? x / y : (x - y + 1) / y); }
template<class T> pair<T, T> divmod(T x, T y) { T q = floor_div(x, y); return {q, x - q * y}; } /// (q, r) s.t. x = q*y + r
ll GCD(ll a, ll b) { if(a < b) swap(a, b); if(b == 0) return a; if(a%b == 0) return b; else return GCD(b, a%b); }
ll LCM(ll a, ll b) { assert(GCD(a,b) != 0); return a / GCD(a, b) * b; }
ll MOD(ll &x, const ll P) { ll ret = x%P; if(ret < 0) ret += P; return x = ret; } /// x % P を非負整数に直す
ll mpow(ll x, ll n, const ll mod) { x %= mod; ll ret = 1; while(n > 0) { if(n & 1) ret = ret * x % mod; x = x * x % mod; n >>= 1; } return ret; } /// x^n % mod を計算
ll lpow(ll x, ll n) { ll ret = 1; while(n > 0){ if(n & 1) ret = ret * x; x = x * x; n >>= 1; } return ret; } /// x^nを計算
string toBinary(ll n) { if(n == 0) return "0"; assert(n > 0); string ret; while (n != 0){ ret += ( (n & 1) == 1 ? '1' : '0' ); n >>= 1; } reverse(ret.begin(), ret.end()); return ret; } /// 10進数(long long) -> 2進数(string)への変換
ll toDecimal(string S) { ll ret = 0; for(int i = 0; i < (int)S.size(); i++){ ret *= 2LL; if(S[i] == '1') ret += 1; } return ret; } /// 2進数(string) → 10進数(long long)への変換
int ceil_pow2(ll n) { int x = 0; while ((1ll << x) < n) x++; return x;} /// return minimum non-negative `x` s.t. `n <= 2**x`
int floor_pow2(ll n) { int x = 0; while ((1ll << (x+1)) <= n) x++; return x;} /// return maximum non-negative `x` s.t. `n >= 2**x`
#include <unistd.h>
// yosupo-san arigatou
namespace yosupo_IO {
template <class T>
using is_signed_int128 =
typename std::conditional<is_same<T, __int128_t>::value
|| is_same<T, __int128>::value,
true_type, false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<is_same<T, __uint128_t>::value
|| is_same<T, unsigned __int128>::value,
true_type, false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<is_same<T, __int128_t>::value, __uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value
|| is_signed_int128<T>::value
|| is_unsigned_int128<T>::value,
true_type, false_type>::type;
template <class T>
using is_signed_int =
typename std::conditional<(is_integral<T>::value
&& std::is_signed<T>::value)
|| is_signed_int128<T>::value,
true_type, false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value
&& std::is_unsigned<T>::value)
|| is_unsigned_int128<T>::value,
true_type, false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value, make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value, std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <class T>
using is_integral_t = enable_if_t<is_integral<T>::value>;
template <class T>
using is_signed_int_t = enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = enable_if_t<is_unsigned_int<T>::value>;
namespace detail {
template <typename T, decltype(&T::is_modint) = &T::is_modint>
std::true_type check_value(int);
template <typename T>
std::false_type check_value(long);
} // namespace detail
template <typename T>
struct is_modint : decltype(detail::check_value<T>(0)) {};
template <typename T>
using is_modint_t = enable_if_t<is_modint<T>::value>;
template <class T>
using to_unsigned_t = typename to_unsigned<T>::type;
struct Scanner {
public:
Scanner(const Scanner &) = delete;
Scanner &operator=(const Scanner &) = delete;
Scanner(FILE *fp) : fd(fileno(fp)) { line[0] = 127; }
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T>
int read_unsafe(H &h, T &... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
int close() { return ::close(fd); }
private:
static constexpr int SIZE = 1 << 15;
int fd = -1;
array<char, SIZE + 1> line;
int st = 0, ed = 0;
bool eof = false;
bool read_single(string &ref) {
if (!skip_space()) return false;
ref = "";
while (true) {
char c = top();
if (c <= ' ') break;
ref += c;
st++;
}
return true;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
template <class T, enable_if_t<is_same<T, char>::value> * = nullptr>
bool read_single(T &ref) {
if (!skip_space<50>()) return false;
ref = top();
st++;
return true;
}
template <class T, is_signed_int_t<T> * = nullptr,
enable_if_t<!is_same<T, char>::value> * = nullptr>
bool read_single(T &sref) {
using U = to_unsigned_t<T>;
if (!skip_space<50>()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
U ref = 0;
do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0');
sref = neg ? -ref : ref;
return true;
}
template <class U, is_unsigned_int_t<U> * = nullptr,
enable_if_t<!is_same<U, char>::value> * = nullptr>
bool read_single(U &ref) {
if (!skip_space<50>()) return false;
ref = 0;
do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0');
return true;
}
bool reread() {
if (ed - st >= 50) return true;
if (st > SIZE / 2) {
std::memmove(line.data(), line.data() + st, ed - st);
ed -= st;
st = 0;
}
if (eof) return false;
auto u = ::read(fd, line.data() + ed, SIZE - ed);
if (u == 0) {
eof = true;
line[ed] = '\0';
u = 1;
}
ed += int(u);
line[ed] = char(127);
return true;
}
char top() {
if (st == ed) {
bool f = reread();
assert(f);
}
return line[st];
}
template <int TOKEN_LEN = 0>
bool skip_space() {
while (true) {
while (line[st] <= ' ') st++;
if (ed - st > TOKEN_LEN) return true;
if (st > ed) st = ed;
for (auto i = st; i < ed; i++) {
if (line[i] <= ' ') return true;
}
if (!reread()) return false;
}
}
};
struct Printer {
public:
template <char sep = ' ', bool F = false>
void write() {}
template <char sep = ' ', bool F = false, class H, class... T>
void write(const H &h, const T &... t) {
if (F) write_single(sep);
write_single(h);
write<true>(t...);
}
template <char sep = ' ', class... T>
void writeln(const T &... t) {
write<sep>(t...);
write_single('\n');
}
Printer(FILE *_fp) : fd(fileno(_fp)) {}
~Printer() { flush(); }
int close() {
flush();
return ::close(fd);
}
void flush() {
if (pos) {
auto res = ::write(fd, line.data(), pos);
assert(res != -1);
pos = 0;
}
}
private:
static array<array<char, 2>, 100> small;
static array<unsigned long long, 20> tens;
static constexpr size_t SIZE = 1 << 15;
int fd;
array<char, SIZE> line;
size_t pos = 0;
std::stringstream ss;
template <class T, enable_if_t<is_same<char, T>::value> * = nullptr>
void write_single(const T &val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, is_signed_int_t<T> * = nullptr,
enable_if_t<!is_same<char, T>::value> * = nullptr>
void write_single(const T &val) {
using U = to_unsigned_t<T>;
if (val == 0) {
write_single('0');
return;
}
if (pos > SIZE - 50) flush();
U uval = val;
if (val < 0) {
write_single('-');
uval = -uval;
}
write_unsigned(uval);
}
template <class T, is_modint_t<T> * = nullptr>
void write_single(const T &val) {
write_single(val.val);
}
static int bsr(unsigned int n) {
return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);
}
static int bsr(unsigned long n) {
return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);
}
static int bsr(unsigned long long n) {
return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);
}
template <class U, is_unsigned_int_t<U> * = nullptr>
void write_single(U uval) {
if (uval == 0) {
write_single('0');
return;
}
if (pos > SIZE - 50) flush();
write_unsigned(uval);
}
template <class U, is_unsigned_int_t<U> * = nullptr>
static int calc_len(U x) {
int i = (bsr(1ULL * x) * 3 + 3) / 10;
if (x < tens[i])
return i;
else
return i + 1;
}
template <class U, is_unsigned_int_t<U> * = nullptr,
enable_if_t<2 >= sizeof(U)> * = nullptr>
void write_unsigned(U uval) {
size_t len = calc_len(uval);
pos += len;
char *ptr = line.data() + pos;
while (uval >= 100) {
ptr -= 2;
memcpy(ptr, small[uval % 100].data(), 2);
uval /= 100;
}
if (uval >= 10) {
memcpy(ptr - 2, small[uval].data(), 2);
} else {
*(ptr - 1) = char('0' + uval);
}
}
template <class U, is_unsigned_int_t<U> * = nullptr,
enable_if_t<4 == sizeof(U)> * = nullptr>
void write_unsigned(U uval) {
array<char, 8> buf;
memcpy(buf.data() + 6, small[uval % 100].data(), 2);
memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2);
memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2);
memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2);
if (uval >= 100000000) {
if (uval >= 1000000000) {
memcpy(line.data() + pos, small[uval / 100000000 % 100].data(), 2);
pos += 2;
} else {
line[pos] = char('0' + uval / 100000000);
pos++;
}
memcpy(line.data() + pos, buf.data(), 8);
pos += 8;
} else {
size_t len = calc_len(uval);
memcpy(line.data() + pos, buf.data() + (8 - len), len);
pos += len;
}
}
template <class U, is_unsigned_int_t<U> * = nullptr,
enable_if_t<8 == sizeof(U)> * = nullptr>
void write_unsigned(U uval) {
size_t len = calc_len(uval);
pos += len;
char *ptr = line.data() + pos;
while (uval >= 100) {
ptr -= 2;
memcpy(ptr, small[uval % 100].data(), 2);
uval /= 100;
}
if (uval >= 10) {
memcpy(ptr - 2, small[uval].data(), 2);
} else {
*(ptr - 1) = char('0' + uval);
}
}
template <class U, enable_if_t<is_unsigned_int128<U>::value> * = nullptr>
void write_unsigned(U uval) {
static array<char, 50> buf;
size_t len = 0;
while (uval > 0) {
buf[len++] = char((uval % 10) + '0');
uval /= 10;
}
std::reverse(buf.begin(), buf.begin() + len);
memcpy(line.data() + pos, buf.data(), len);
pos += len;
}
void write_single(const std::string &s) {
for (char c: s) write_single(c);
}
void write_single(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write_single(s[i]);
}
template <class T>
void write_single(const std::vector<T> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write_single(' ');
write_single(val[i]);
}
}
};
array<array<char, 2>, 100> Printer::small = [] {
array<array<char, 2>, 100> table;
for (int i = 0; i <= 99; i++) {
table[i][1] = char('0' + (i % 10));
table[i][0] = char('0' + (i / 10 % 10));
}
return table;
}();
array<ull, 20> Printer::tens = [] {
array<ull, 20> table;
for (int i = 0; i < 20; i++) {
table[i] = 1;
for (int j = 0; j < i; j++) { table[i] *= 10; }
}
return table;
}();
} // namespace yosupo_IO
using namespace yosupo_IO;
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
// ############################
// # #
// # C O D E S T A R T #
// # #
// ############################
/// 有理数型 (x/y)
// 分母分子が longlong 内に収まっても、比較の際の乗算でオーバーフローする可能性があることに注意 -> T = i128を使う
template< class T = long long>
class Fraction{
public:
T x,y;
/// 約分
void reduc(){
int minus = 1;
T absx = x;
T absy = y;
if(x < 0) minus *= -1, absx *= -1;
if(y < 0) minus *= -1, absy *= -1;
T g = gcd(absx, absy);
x = minus * absx / g;
y = absy / g;
}
Fraction(T x = 0, T y = 1): x(x), y(y) {reduc();};
// 比較の際の乗算でオーバーフローすることがあることに注意
bool operator<(const Fraction& right) const {return x*right.y < y*right.x;}
bool operator<=(const Fraction& right) const {return x*right.y <= y*right.x;}
bool operator>(const Fraction& right) const {return x*right.y > y*right.x;}
bool operator>=(const Fraction& right) const {return x*right.y >= y*right.x;}
bool operator==(const Fraction& right) const {return x == right.x && y == right.y;}
Fraction operator-() const {return Fraction(-x, y);}
Fraction& operator+=(const Fraction& v){
x = x*v.y + y*v.x;
y *= v.y;
reduc();
return *this;
}
Fraction operator+(const Fraction& v) const {return Fraction(*this) += v;}
Fraction& operator-=(const Fraction& v){
x = x*v.y - y*v.x;
y *= v.y;
reduc();
return *this;
}
Fraction operator-(const Fraction& v) const {return Fraction(*this) -= v;}
Fraction& operator*=(const Fraction& v){
x *= v.x;
y *= v.y;
reduc();
return *this;
}
Fraction operator*(const Fraction& v) const {return Fraction(*this) *= v;}
Fraction& operator/=(const Fraction& v){
x *= v.y;
y *= v.x;
reduc();
return *this;
}
Fraction operator/(const Fraction& v) const {return Fraction(*this) /= v;}
Fraction inv() const {return Fraction(y,x);}
Fraction pow(long long t) const {
if(t < 0) return inv().pow(-t);
Fraction a(1, 1), d = *this;
while(t){
d *= d;
if(t & 1) a *= d;
t >>= 1;
}
return a;
}
friend ostream& operator << (ostream& os, const Fraction& v){ return os << v.x << '/' << v.y;}
private:
T gcd(T a, T b){
if(a < b) swap(a, b);
if(b == 0) return a;
if(a%b == 0) return b;
else return gcd(b, a%b);
}
};
#include<boost/multiprecision/cpp_int.hpp>
using Fractionll = Fraction<boost::multiprecision::cpp_int>;
using namespace boost::multiprecision;
void YesNo(bool b) {if(b){printer.writeln("Yes");} else{printer.writeln("No");}}
// https://www.mynote-jp.com/entry/Circle-Defined-by-Three-Points
void solve() {
int Q; scanner.read(Q);
vi X(3);
vi Y(3);
rep(i,3) scanner.read(X[i], Y[i]);
int a = X[0] - X[1];
int b = Y[0] - Y[1];
int c = X[1] - X[2];
int d = Y[1] - Y[2];
ll bunbo = 2 * (a * d - b * c);
debug(bunbo);
if(bunbo == 0) {
vpll XY(3); rep(i,3) XY[i] = {X[i],Y[i]};
sort(all(XY));
ll cx = XY[1].first;
ll cy = XY[1].second;
ll r2 = square(X[0] - cx) + square(Y[0] - cy);
while(Q--) {
ll x,y; scanner.read(x, y);
ll dist = square(x - cx) + square(y - cy);
YesNo(dist <= r2);
}
return;
}
ll e = square(X[0]) + square(Y[0]) - (square(X[1]) + square(Y[1]));
ll f = square(X[1]) + square(Y[1]) - (square(X[2]) + square(Y[2]));
Fractionll cx(d*e - b*f, bunbo);
Fractionll cy(-c*e + a*f, bunbo);
Fractionll r2 = square(Fractionll(X[0],1) - cx) + square(Fractionll(Y[0],1) - cy);
cpp_int ir2 = r2.x / r2.y;
debug(cx,cy,r2);
while(Q--) {
int x,y; scanner.read(x, y);
Fractionll dist = square(Fractionll(x,1) - cx) + square(Fractionll(y,1) - cy);
cpp_int id = dist.x/dist.y;
if(id == ir2) {
cpp_int p = dist.x * r2.y;
cpp_int q = dist.y * r2.x;
//YesNo(dist <= r2);
YesNo(p <= q);
}
else YesNo(id < ir2);
}
}
signed main() {
cin.tie(0); ios_base::sync_with_stdio(false);
TIMER_START;
//cout << fixed << setprecision(15);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
TIMECHECK;
return 0;
}