#881987 (C++17) No.2353 Guardian Dogs in Spring

提出ソース
結果

問題	No.2353 Guardian Dogs in Spring
ユーザー	aplysiaSheep
提出日時	2023-06-16 22:39:10
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	21,552 bytes
コンパイル時間	5,284 ms
コンパイル使用メモリ	288,832 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-24 15:24:26
合計ジャッジ時間	50,685 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	1,560 ms 6,944 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	64 ms 6,944 KB
testcase_22	AC	403 ms 6,940 KB
testcase_23	AC	1,846 ms 6,940 KB
testcase_24	AC	54 ms 6,940 KB
testcase_25	AC	39 ms 6,940 KB
testcase_26	AC	27 ms 6,940 KB
testcase_27	AC	4 ms 6,944 KB
testcase_28	AC	89 ms 6,944 KB
testcase_29	AC	887 ms 6,940 KB
testcase_30	AC	435 ms 6,940 KB
testcase_31	AC	713 ms 6,940 KB
testcase_32	AC	1,884 ms 6,940 KB
testcase_33	AC	1,778 ms 6,940 KB
testcase_34	AC	1,806 ms 6,940 KB
testcase_35	AC	1,835 ms 6,944 KB
testcase_36	WA	-
testcase_37	WA	-
testcase_38	AC	140 ms 6,940 KB
testcase_39	AC	165 ms 6,944 KB
testcase_40	AC	592 ms 6,944 KB
testcase_41	AC	689 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

#define int long long
// #define endl "\n"

#pragma GCC optimize("-O3")

void solve();

typedef long long ll;
typedef __int128_t LL;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, pair<int, int>> pip;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<pair<int, int>> vp;
typedef vector<vector<int>> vvi;
typedef vector<vector<double>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<pair<int, int>>> vvp;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
template <typename T>
using vec = vector<T>;
template <typename T>
using vv = vector<vector<T>>;
template <typename T>
using vvv = vector<vector<vector<T>>>;
template <typename T>
using vvvv = vector<vector<vector<vector<T>>>>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using mset = multiset<T>;
template <typename T>
using uset = unordered_set<T>;
template <typename T, typename U>
using umap = unordered_map<T, U>;

#define _PI 3.14159265358979323846
#define _E 2.7182818284590452354
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define td typedef
#define elif else if
#define ifnot(x) if(!(x))
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define sumv(a) accumulate(all(a), 0LL)
#define lb(v, a) (lower_bound(begin(v), end(v), a) - begin(v))
#define ub(v, a) (upper_bound(begin(v), end(v), a) - begin(v))
#define inr(l, x, r) (l <= x && x < r)
#define cbit(x) __builtin_popcountll(x)
#define topbit(t) (t == 0 ? -1 : 63 - __builtin_clzll(t))
#define botbit(t) (t == 0 ? 64 : __builtin_ctzll(t))
#define gbit(msk, i) ((msk) >> (i)&1)
#define mask(x) ((1LL << (x)) - 1)
#define setbits(i, n) \
    for(int j = (n), i = botbit(j); j; j ^= 1LL << i, i = botbit(j))

#define rep1(a) for(int i = 0; i < (int)a; i++)
#define rep2(i, a) for(int i = 0; i < (int)a; 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 overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = n; i--;)
#define rrep2(i, n) for(ll i = n; i--;)
#define rrep3(i, a, b) for(ll i = b; i-- > (a);)
#define rrep4(i, a, b, c) \
    for(ll i = (a) + ((b) - (a)-1) / (c) * (c); i >= (a); i -= c)
#define rrep(...) \
    overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define fore1(i, a) for(auto &&i : a)
#define fore2(x, y, a) for(auto &&[x, y] : a)
#define fore3(x, y, z, a) for(auto &&[x, y, z] : a)
#define fore(...) overload4(__VA_ARGS__, fore3, fore2, fore1)(__VA_ARGS__)
#define ryes return yes();
#define rno return no();
#define rerr return err();

istream &operator>>(istream &is, modint998244353 &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
ostream &operator<<(ostream &os, const modint998244353 &a) {
    return os << a.val();
}
istream &operator>>(istream &is, modint1000000007 &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
ostream &operator<<(ostream &os, const modint1000000007 &a) {
    return os << a.val();
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << "," << p.second;
    return os;
}
template <class T>
ostream &operator<<(ostream &s, set<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, map<T1, T2> P) {
    fore(x, y, P) {
        s << "<" << x << "->" << y << "> ";
    }
    return s;
}
template <class T>
ostream &operator<<(ostream &s, multiset<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T>
ostream &operator<<(ostream &s, unordered_set<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, unordered_map<T1, T2> P) {
    fore(x, y, P) {
        s << "<" << x << "->" << y << "> ";
    }
    return s;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for(auto &e : v) is >> e;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(auto &e : v) os << e << ' ';
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
    for(auto &e : v) {
        for(auto &c : e) os << c << ' ';
        os << endl;
    }
    return os;
}
template <class T>
vector<T> &operator++(vector<T> &v) {
    for(auto &e : v) e++;
    return v;
}
template <class T>
vector<T> operator++(vector<T> &v, signed) {
    auto res = v;
    for(auto &e : v) e++;
    return res;
}
template <class T>
vector<T> &operator--(vector<T> &v) {
    for(auto &e : v) e--;
    return v;
}
template <class T>
vector<T> operator--(vector<T> &v, signed) {
    auto res = v;
    for(auto &e : v) e--;
    return res;
}

// 十進数からb進数へ
template <class T>
string to_baseB(T x, int b = 10) {
    string ans;
    do {
        int num = x % b;
        ans = (char)((num <= 9) ? ('0' + num) : ('A' + num - 10)) + ans;
        x /= b;
    } while(x != 0);
    return ans;
}
// b進数から十進数へ
long long to_base10(const string &x, int b = 10) {
    long long ans = 0, base = 1;
    for(int i = x.length() - 1; i >= 0; --i) {
        int num =
            ('0' <= x[i] && x[i] <= '9') ? (x[i] - '0') : (x[i] - 'A' + 10);
        ans += base * num;
        base *= b;
    }
    return ans;
}

ostream &operator<<(ostream &s, const LL &p) {
    s << to_baseB(p);
    return s;
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3)                                                 \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << endl
#define debug_4(x1, x2, x3, x4)                                             \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5)                                         \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

void out() {
    cout << endl;
}
template <class T>
void out(const T &a) {
    cout << a;
    cout << endl;
}
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << endl;
}
#define rout_1(x1) return out(x1)
#define rout_2(x1, x2) return out(x1, x2)
#define rout_3(x1, x2, x3) return out(x1, x2, x3)
#define rout_4(x1, x2, x3, x4) return out(x1, x2, x3, x4)
#define rout_5(x1, x2, x3, x4, x5) return out(x1, x2, x3, x4, x5)
#define rout(...)                                                    \
    CHOOSE((__VA_ARGS__, rout_5, rout_4, rout_3, rout_2, rout_1, ~)) \
    (__VA_ARGS__)

struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
    };
} fast_ios_;

struct Binomial {
    int p;
    int MAX;
    vector<long long> fac, finv, inv;

    // テーブルを作る前処理
    Binomial(int p_, int n = 1) : p(p_), MAX(1), fac(2), finv(2), inv(2) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        if(n != 1) build(n);
    }

    void build(int new_max) {
        MAX++;
        fac.resize(new_max + 1);
        inv.resize(new_max + 1);
        finv.resize(new_max + 1);
        for(; MAX <= new_max; MAX++) {
            fac[MAX] = fac[MAX - 1] * MAX % p;
            inv[MAX] = p - inv[p % MAX] * (p / MAX) % p;
            finv[MAX] = finv[MAX - 1] * inv[MAX] % p;
        }
        MAX--;
    }

    // nCk
    long long mod_comb(int n, int k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        if(n > MAX) build(n);
        return fac[n] * (finv[k] * finv[n - k] % p) % p;
    }
    long long operator()(int n, int k) {
        return mod_comb(n, k);
    }

    // nPk
    long long mod_perm(int n, int k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        if(n > MAX) build(n);
        return fac[n] * finv[n - k] % p;
    }
    long long operator[](int n) {
        return mod_perm(n, n);
    }
};

struct modpow {
    long long x, m;
    int n;
    vector<long long> d;
    modpow(long long x, long long m = 0) : x(x), m(m), n(1), d(1, 1) {}
    long long operator[](int i) {
        if(m)
            while(n <= i) d.push_back(d.back() * x % m), ++n;
        else
            while(n <= i) d.push_back(d.back() * x), ++n;
        return d[i];
    }
} two(2), ten(10);

struct RandomNumberGenerator {
    mt19937 mt;

    RandomNumberGenerator()
        : mt(chrono::steady_clock::now().time_since_epoch().count()) {}

    long long operator()(long long a, long long b) {  // [a, b)
        uniform_int_distribution<long long> dist(a, b - 1);
        return dist(mt);
    }

    long long operator()(long long b) {  // [0, b)
        return (*this)(0, b);
    }

    long long operator()() {
        return (*this)(0, 1LL << 60);
    }

    double operator[](double a) {
        return (double)(*this)(0, 1LL << 60) / (1LL << 60) * a;
    }
} rnd;

clock_t start_time = clock();
double now_time() {
    clock_t end_time = clock();
    return (double)(end_time - start_time) / CLOCKS_PER_SEC;
}

void input_graph(vector<vector<int>> &g, int m = -1, int bidirected = true) {
    if(m == -1) m = g.size() - 1;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        if(bidirected) g[v].push_back(u);
    }
}
vector<int> iota(int n, int s = 0) {
    vi a(n);
    iota(a.begin(), a.end(), s);
    return a;
}
template <class T>
void sort(vector<T> &v) {
    sort(all(v));
}
template <class T>
void rsort(vector<T> &v) {
    sort(rall(v));
}
template <class T>
void reverse(T &v) {
    reverse(all(v));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
long long max(signed x, long long y) {
    return max((long long)x, y);
}
long long max(long long x, signed y) {
    return max(x, (long long)y);
}
long long min(signed x, long long y) {
    return min((long long)x, y);
}
long long min(long long x, signed y) {
    return min(x, (long long)y);
}
template <class T, class S>
bool chmax(T &a, const S &b) {
    if(a < (T)b) {
        a = (T)b;
        return 1;
    }
    return 0;
}
template <class T, class S>
bool chmin(T &a, const S &b) {
    if((T)b < a) {
        a = (T)b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> uniq(vector<T> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v;
}
template <class T>
vector<T> compress(vector<T> v) {
    vector<T> v2(v.size());
    v2 = v;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 0; i < (int)v2.size(); i++) {
        v2[i] = lower_bound(v.begin(), v.end(), v2[i]) - v.begin();
    }
    return v2;
}
vector<int> inverse(vector<int> &p) {
    int n = p.size();
    vector<int> inv(n);
    for(int i = 0; i < n; i++) inv[p[i]] = i;
    return inv;
}
template <typename T>
vector<T> acc0(vector<T> &v) {
    vector<T> res(v.size());
    if((int)v.size() == 0) return res;
    res[0] = v[0];
    for(int i = 1; i < (int)v.size(); i++) {
        res[i] = res[i - 1] + v[i];
    }
    return res;
}
template <typename T>
vector<T> acc1(vector<T> &v) {
    vector<T> res(v.size() + 1);
    for(int i = 0; i < (int)v.size(); i++) {
        res[i + 1] = res[i] + v[i];
    }
    return res;
}
template <typename T>
vector<vector<T>> acc0(vector<vector<T>> v) {
    int h = v.size(), w = v[0].size();
    for(int i = 0; i < h; i++) {
        for(int j = 1; j < w; j++) {
            v[i][j] += v[i][j - 1];
        }
    }
    for(int i = 1; i < h; i++) {
        for(int j = 0; j < w; j++) {
            v[i][j] += v[i - 1][j];
        }
    }
    return v;
}
template <typename T>
vector<vector<T>> acc1(vector<vector<T>> &v) {
    int h = v.size(), w = v[0].size();
    vector<vector<T>> res(h + 1, vector<T>(w + 1));
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            res[i + 1][j + 1] = v[i][j] + res[i + 1][j];
        }
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            res[i + 1][j + 1] += res[i][j + 1];
        }
    }
    return res;
}
long long exp(long long x, int n) {
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * x;
        x = x * x;
        n >>= 1;
    }
    return res;
}
int countDigits(long long n) {
    string tmp = to_string(n);
    return (int)tmp.size();
}
long long sq(long long n) {
    return n * n;
}
long long ceil(long long x, long long y) {
    return (x + y - 1) / y;
}
long long floor(long long x, long long y) {
    return (y < 0 ? floor(-x, -y)
                  : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
constexpr long long tri(long long n) {
    return n * (n + 1) / 2;
}
// l + ... + r
constexpr long long tri(long long l, long long r) {
    return (l + r) * (r - l + 1) / 2;
}
int ctoi(const char &c, const char start = '0') {
    return c - start;
}
int atoi(const char &c, const char start = 'a') {
    return c - start;
}
vector<int> ctoi(string &s, const char start = '0') {
    vector<int> res;
    for(auto &c : s) {
        int x = c - start;
        if(x < 0 || x >= 10) x = -1;
        res.push_back(x);
    }
    return res;
}
vector<int> atoi(string &s, const char start = 'a') {
    vector<int> res;
    for(auto &c : s) {
        int x = c - start;
        if(x < 0 || x >= 26) x = -1;
        res.push_back(x);
    }
    return res;
}
void yes() {
    cout << "Yes" << endl;
}
void no() {
    cout << "No" << endl;
}
void yesno(bool x) {
    if(x)
        yes();
    else
        no();
}
void err() {
    cout << -1 << endl;
}

int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

long long inf = 1LL << 61;
double eps = 1e-9;

// long long mod = 67280421310721;
// using mint = static_modint<1000000009>;
// using mint = dynamic_modint<1000000009>;
// long long mod = 1000000007;
// using mint = modint1000000007;
// long long mod = 998244353;
// using mint = modint998244353;
// typedef vector<mint> vm;
// typedef vector<vector<mint>> vvm;
// typedef vector<vector<vector<mint>>> vvvm;
// Binomial C(mod);
// modpow mtwo(2, mod), mten(10, mod);
////////////////////////////////////////////////////////////////////////////////////////////
/*
蟻本p226より
二次元構造体P(ll x,ll y)は,
.dotで内積
.detで外積をとる。

比較演算子はx座標の昇順。偏角ソートに変えるには#define Declination_sortをオンに

bool on_seg(P p1,P p2,P q)：線分p1-p2上に点qがあるか判定
P intersection(P p1,P p2,P q1,P q2):直線p1-p2と直線q1-q2の交点
bool parallel(P p1, P p2, P q1, P q2):直線p1-p2と直線q1-q2が並行かどうか
ll dist(P p,P q):点p、点qの距離の二乗
vector<P> convext_hull(P*ps,int n):凸包を求める。(nは頂点数)
*/

// 二次元ベクトル構造体
// #define Declination_sort  // 偏角ソート
struct P {
    long long x, y;
    P() {}
    P(long long x, long long y) : x(x), y(y) {}

    int ort() const {
        if(x == 0 && y == 0) return 0;
        if(y > 0)
            return x > 0 ? 1 : 2;
        else
            return x > 0 ? 4 : 3;
    }

    long long norm2() const {
        return x * x + y * y;
    }
    double norm() const {
        return sqrt(norm2());
    }
    P rotate90() const {
        return P(y, -x);
    }

    P operator+(P p) {
        return P(x + p.x, y + p.y);
    }
    P &operator+=(const P &other) {
        *this = (*this) + other;
        return *this;
    }
    P operator-(P p) {
        return P(x - p.x, y - p.y);
    }
    P &operator-=(const P &other) {
        *this = (*this) - other;
        return *this;
    }
    P operator*(long long d) {
        return P(x * d, y * d);
    }
    P &operator*=(const long long d) {
        *this = (*this) * d;
        return *this;
    }
    P operator/(long long d) {
        return P(x / d, y / d);
    }
    P &operator/=(long long d) {
        *this = (*this) / d;
        return *this;
    }
    long long dot(P p) const {  // 内積
        return x * p.x + y * p.y;
    }
    long long det(P p) const {  // 外積
        return x * p.y - y * p.x;
    }
    bool operator==(const P &other) const {
        if(x == other.x && y == other.y) return true;
        return false;
    }
    bool operator!=(const P &other) const {
        if((*this) == other) return false;
        return true;
    }

#ifdef Declination_sort
    // 偏角ソート 同一直線上は中心が近いものが先
    bool operator<(const P &p) const {
        int o = ort(), vo = p.ort();
        if(o != vo) return o < vo;
        if(det(p) == 0) return norm2() < p.norm2();
        return det(p) > 0;
    }
    bool operator>(const P &p) const {
        int o = ort(), vo = p.ort();
        if(o != vo) return o > vo;
        if(det(p) == 0) return norm2() > p.norm2();
        return det(p) < 0;
    }
#else
    // 左下から右上へ
    bool operator<(const P &other) const {
        if(x != other.x) return x < other.x;
        return y < other.y;
    }
    bool operator>(const P &other) const {
        if(x != other.x) return x > other.x;
        return y > other.y;
    }
#endif

    // 線分p1-p2上に点qがあるか判定
    friend bool on_seg(P p1, P p2, P q) {
        return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0;
    }

    // 直線p1-p2と直線q1-q2が並行かどうか
    friend bool parallel(P p1, P p2, P q1, P q2) {
        return (p1 - p2).det(q1 - q2) == 0;
    }

    // 距離の二乗を求める
    friend long long dist2(P p, P q) {
        return (p - q).dot(p - q);
    }
    friend double dist(P p, P q) {
        return sqrt(dist2(p, q));
    }

    // 凸包を求める。
    friend vector<P> convex_hull(vector<P> ps) {
        int n = ps.size();
        sort(ps.begin(), ps.end());
        int k = 0;
        vector<P> qs(n * 2);
        for(int i = 0; i < n; i++) {
            while(k > 1 && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) < 0)
                k--;
            qs[k++] = ps[i];
        }
        for(int i = n - 2, t = k; i >= 0; i--) {
            while(k > t && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) < 0)
                k--;
            qs[k++] = ps[i];
        }
        qs.resize(k - 1);
        return qs;
    }

    friend istream &operator>>(istream &is, P &p) {
        is >> p.x >> p.y;
        return is;
    }

    friend ostream &operator<<(ostream &os, const P &p) {
        os << p.x << " " << p.y << endl;
        return (os);
    }
};

// https://youtu.be/UWbGRhF3Ozw?t=9564
struct Line {
    P s, t;
    Line(P s = P(), P t = P()) : s(s), t(t) {}
    P dir() {
        return t - s;
    }
    double norm() {
        return dir().norm();
    }
    /* +1: s-t,s-p : ccw(反時計回り)
     * -1: s-t,s-p : cw(時計回り)
     * +2: t-s-p : s!=p
     * -2: s-t-p :t!=p
     *  0: s-p-t */
    int ccw(P p) {
        if(dir().det(p - s) > 0) return +1;
        if(dir().det(p - s) < 0) return -1;
        if(dir().dot(p - s) < 0) return +2;
        if(dir().norm2() < (p - s).norm2()) return -2;
        return 0;
    }
};
////////////////////////////////////////////////////////////////////////////////////////////

signed main() {
    int testcase = 1;
    // cin >> testcase;
    for(int i = 0; i < testcase; i++) {
        solve();
    }
}

void solve() {
    int n;
    cin >> n;
    vi x(n), y(n);
    map<P, int> mem;
    rep(i, n) {
        cin >> x[i] >> y[i];
        mem[{x[i], y[i]}] = i;
    }
    vi used(n);
    int cnt = n;
    vp ans;
    while(cnt > 1) {
        vector<P> tmp;
        rep(i, n) {
            if(used[i]) continue;
            tmp.push_back({x[i], y[i]});
        }

        auto c = convex_hull(tmp);
        debug(c);
        int t = 0;
        int s = c.size();
        while((c[t] - c[(2 * t - 1) % s]).det((c[(t + 1) % s] - c[t]))) {
            t++;
        }
        int l = mem[c[t]];
        int r = mem[c[(t + 1) % s]];
        debug(l, r);
        ans.push_back({l, r});
        debug(ans);
        used[l] = 1;
        used[r] = 1;
        cnt -= 2;
    }

    out(ans.size());
    for(auto [x, y] : ans) {
        out(x + 1, y + 1);
    }
}
yukicoder

結果

テストケース

ソースコード
