QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177279 | #6875. Chaos Begin | PPP# | AC ✓ | 1385ms | 12708kb | C++17 | 3.1kb | 2023-09-12 19:44:20 | 2023-09-12 19:44:20 |
Judging History
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
const int maxN = 100'005;
ll x[2][maxN];
void solve() {
cin >> n;
for (int i = 1; i <= 2 * n; i++) {
cin >> x[0][i] >> x[1][i];
}
vector<ll> F[2];
for (int it = 0; it < 2; it++) {
vector<ll> X;
for (int i = 1; i <= 2 * n; i++) {
X.emplace_back(x[it][i]);
}
sort(X.begin(), X.end());
vector<ll> cands;
for (int i = 2; i <= 2 * n; i++) {
cands.emplace_back(x[it][i] - x[it][1]);
cands.emplace_back(-cands.back());
}
sort(cands.begin(), cands.end());
cands.erase(unique(cands.begin(), cands.end()), cands.end());
for (ll d : cands) {
// cout << " CHECK " << d << " " << it << endl;
bool ok = true;
for (int u = 1; u <= 2 * n; u++) {
int p = lower_bound(X.begin(), X.end(), x[it][u] + d) - X.begin();
if (p < X.size() && X[p] == x[it][u] + d) continue;
p = lower_bound(X.begin(), X.end(), x[it][u] - d) - X.begin();
if (p < X.size() && X[p] == x[it][u] - d) continue;
ok = false;
break;
}
if (ok) {
// cout << " ADD " << it << " " << d << endl;
F[it].emplace_back(d);
}
}
}
assert(!F[0].empty());
assert(!F[1].empty());
vector<pair<ll,ll>> ans;
for (ll ddx : F[0]) {
for (ll ddy : F[1]) {
ll dx = ddx;
ll dy = ddy;
// cout << dx << " " << dy << " HIHIHI " << endl;
multiset<pair<ll,ll>> S;
ll ini_x = dx, ini_y = dy;
ll coef_x = 1;
if (dx < 0) {
coef_x *= -1;
dx *= -1;
}
ll coef_y = 1;
if (dy < 0) {
coef_y *= -1;
dy *= -1;
}
for (int i = 1; i <= 2 * n; i++) {
S.insert({x[0][i] * coef_x, x[1][i] * coef_y});
}
bool good = true;
while (!S.empty()) {
auto it = *S.begin();
S.erase(S.find(it));
if (S.find({it.first + dx, it.second + dy}) == S.end()) {
good = false;
break;
}
S.erase(S.find({it.first + dx, it.second + dy}));
}
if (good) {
ans.emplace_back(ini_x, ini_y);
}
}
}
assert(!ans.empty());
cout << ans.size() << '\n';
for (auto& it : ans) {
cout << it.first << " " << it.second << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
int tst;
cin >> tst;
while (tst--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1385ms
memory: 12708kb
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