fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using ll = long long;
  4. using namespace std;
  5. using point = pair<int, int>;
  6.  
  7. int dx[] = {0, 0, 1, -1};
  8. int dy[] = {1, -1, 0, 0};
  9. const int N = 1e5;
  10.  
  11. bool is_black(const point& cand) {
  12.     return (cand.first + cand.second) % 2 == 0;
  13. }
  14. bool valid(const point& cand) {
  15.     auto [x, y] = cand;
  16.     return 1 <= x && x <= N && 1 <= y && y <= N;
  17. }
  18.  
  19. vector<pair<int, int>> solve(int n, int flag) {
  20.  
  21.     if (n == 0) {
  22.         return {{1, 2}};
  23.     }
  24.  
  25.     set<point> vis;
  26.     deque<point> q;
  27.     vis.insert({N / 2 + flag, N / 2});
  28.     q.emplace_back(N / 2 + flag, N / 2);
  29.  
  30.     while (!q.empty()) {
  31.         point cur = q.front();
  32.         q.pop_front();
  33.  
  34.         n -= is_black(cur);
  35.         if (!n) break;
  36.  
  37.         for (int k = 0; k < 4; k++) {
  38.             cur.first += dx[k];
  39.             cur.second += dy[k];
  40.  
  41.             if (valid(cur) && vis.find(cur) == vis.end()) {
  42.             	vis.insert(cur);
  43.                 if (is_black(cur)) q.push_front(cur);
  44.                 else q.push_back(cur);
  45.             }
  46.  
  47.             cur.first -= dx[k];
  48.             cur.second -= dy[k];
  49.         }
  50.     }
  51.  
  52.     vector<point> ret;
  53.     for (auto& cand : vis) {
  54.         auto p = cand;
  55.         if (is_black(p)) {
  56.             ret.push_back(p);
  57.             continue;
  58.         }
  59.         int cnt = 0;
  60.         for (int k = 0; k < 4; k++) {
  61.             p.first += dx[k];
  62.             p.second += dy[k];
  63.  
  64.             if (vis.find(p) != vis.end())
  65.                 cnt++;
  66.  
  67.             p.first -= dx[k];
  68.             p.second -= dy[k];
  69.         }
  70.         if (cnt > 1) ret.push_back(p);
  71.     }
  72.  
  73.     return ret;
  74. }
  75.  
  76. int32_t main() {
  77.     ios::sync_with_stdio(false);
  78.     cin.tie(nullptr), cout.tie(nullptr);
  79.  
  80.     int t;
  81.     cin >> t;
  82.  
  83.     while (t--) {
  84.         int n;
  85.         cin >> n;
  86.  
  87.         vector<pair<int, int>> a = solve(n, 0);
  88.         vector<pair<int, int>> b = solve(n, 1);
  89.  
  90.         if (a.size() > b.size()) a = b;
  91.  
  92.         cout << a.size() << "\n";
  93.         for (auto& [i, j] : a) {
  94.  
  95.             cout << i - 49996 << " " << j - 49996 << "\n";
  96.         }
  97.     }
  98.  
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1
12
stdout
copy 
27
2 3
2 4
2 5
3 2
3 3
3 4
3 5
3 6
4 2
4 3
4 4
4 5
4 6
5 2
5 3
5 4
5 5
5 6
6 2
6 3
6 4
6 5
6 6
7 3
7 4
7 5
7 6
https://ideone.com/MVqA5I
language:
C++14 (clang 8.0)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!