QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#177279#6875. Chaos BeginPPP#AC ✓1385ms12708kbC++173.1kb2023-09-12 19:44:202023-09-12 19:44:20

Judging History

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

  • [2023-09-12 19:44:20]
  • 评测
  • 测评结果:AC
  • 用时:1385ms
  • 内存:12708kb
  • [2023-09-12 19:44:20]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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