結果
問題 | No.2353 Guardian Dogs in Spring |
ユーザー | aplysiaSheep |
提出日時 | 2023-06-16 22:53:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 21,722 bytes |
コンパイル時間 | 5,447 ms |
コンパイル使用メモリ | 288,172 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-24 15:51:29 |
合計ジャッジ時間 | 14,789 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 12 ms
6,944 KB |
testcase_06 | AC | 12 ms
6,944 KB |
testcase_07 | AC | 13 ms
6,940 KB |
testcase_08 | AC | 13 ms
6,940 KB |
testcase_09 | AC | 12 ms
6,940 KB |
testcase_10 | WA | - |
testcase_11 | AC | 12 ms
6,940 KB |
testcase_12 | AC | 13 ms
6,940 KB |
testcase_13 | AC | 13 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | AC | 12 ms
6,944 KB |
testcase_34 | AC | 14 ms
6,944 KB |
testcase_35 | AC | 13 ms
6,940 KB |
testcase_36 | AC | 4 ms
6,940 KB |
testcase_37 | AC | 3 ms
6,940 KB |
testcase_38 | AC | 6 ms
6,944 KB |
testcase_39 | AC | 6 ms
6,944 KB |
testcase_40 | AC | 8 ms
6,944 KB |
testcase_41 | AC | 9 ms
6,940 KB |
ソースコード
#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; auto next = [&](P now) { }; 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[(t + s - 1) % s]).det((c[(t + 1) % s] - c[t]))) { t++; } while(1) { int l = mem[c[t]]; int r = mem[c[(t + 1) % s]]; debug(l, r); if(used[l] || used[r]) break; ans.push_back({l, r}); debug(ans); used[l] = 1; used[r] = 1; cnt -= 2; t = (t + 2) % s; } } out(ans.size()); for(auto [x, y] : ans) { out(x + 1, y + 1); } }