QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759503#6875. Chaos Beginwly09AC ✓201ms10216kbC++201.3kb2024-11-18 09:19:352024-11-18 09:19:36

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 09:19:36]
  • 评测
  • 测评结果:AC
  • 用时:201ms
  • 内存:10216kb
  • [2024-11-18 09:19:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

struct hash_pairii {
  int64_t operator()(const pair<int, int> &pr) const {
    return (int64_t)(pr.first) << 32 | pr.second;
  }
};

void solve() {
  vector<pair<int, int>> v;
  unordered_multiset<pair<int, int>, hash_pairii> st;
  int n;
  cin >> n;
  for (int64_t i = 0; i < n << 1; ++i) {
    int64_t x, y;
    cin >> x >> y;
    st.emplace(x, y);
    v.emplace_back(x, y);
  }
  if ([&]() {
        for (const auto &pr : v)
          if (st.count(pr) & 1)
            return false;
        return true;
      }()) {
    cout << "1\n0 0\n";
    return;
  }
  set<pair<int64_t, int64_t>> ans;
  auto check = [&](int64_t x, int64_t y) -> bool {
    if (!x && !y)
      return false;
    for (const auto &[a, b] : v) {
      if (!st.count({a + x, b + y}) && !st.count({a - x, b - y}))
        return false;
    }
    return true;
  };
  for (size_t i = 1; i < v.size(); ++i) {
    int64_t x = v[i].first - v[0].first;
    int64_t y = v[i].second - v[0].second;
    if (check(x, y)) {
      ans.emplace(x, y), ans.emplace(-x, -y);
    }
  }
  cout << ans.size() << '\n';
  for (const auto &[a, b] : ans)
    cout << a << ' ' << b << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 201ms
memory: 10216kb

input:

100
1
828748 -4793083
-4304195 -5463593
3
237233 -4112155
8020574 8746231
435013 -5934194
-864201 -1891603
1536447 -8154746
9319788 4703640
2
-8647149 5511912
94771 -4903783
8836691 -15319478
94771 -4903783
2
4374481 1876187
8834277 -13370279
6604379 -5747046
6604379 -5747046
2
274825 17829398
-4517...

output:

2
-5132943 -670510
5132943 670510
2
-1299214 4042591
1299214 -4042591
2
-8741920 10415695
8741920 -10415695
2
-2229898 7623233
2229898 -7623233
2
-2396328 -13627890
2396328 13627890
2
-6349453 -7699267
6349453 7699267
2
-6444872 4551651
6444872 -4551651
2
-8530514 4791752
8530514 -4791752
2
-8966722...

result:

ok 299 lines