QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461615#6875. Chaos BeginmdubaAC ✓10985ms332108kbC++209.0kb2024-07-02 20:46:452024-07-02 20:46:47

Judging History

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

  • [2024-07-02 20:46:47]
  • 评测
  • 测评结果:AC
  • 用时:10985ms
  • 内存:332108kb
  • [2024-07-02 20:46:45]
  • 提交

answer

//#pragma comment(linker, "/stack:20000000")
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define se second
#define fi first
#define ld long double
#define ss size()
#define pb push_back
#define mp make_pair
#define ins insert
#define ll long long
#define ull unsigned long long
#define y1 y12313312312
#define vd vasvsadasdasfdasf
#define endl '\n'
#define gcd __gcd
#define b_p __builtin_popcountll
#define next nqweqweeqeqe
#define prev ppawfawfpfaw
#define pii pair < int, int >
#define pdd pair < double, double >
#define vi vector < int >
#define vpii vector < pii >
#define vpdd vector < pdd >
#define si set < int >
#define spii set < pii >
#define mii map < int, int >
#define umii unordered_map < int, int >
#define msi multiset < int >
#define qi queue < int >
#define qpii queue < pii >
#define mci map < char, int >
#define mdi map < double, int >
#define all(x) x.begin(), x.end()
#define mems(x, y) memset(x, y, sizeof x)
#define srt(x, y) sort(x + 1, x + y + 1)
#define rvs(x, y) reverse(x + 1, x + y + 1)
#define FOR(i, x, y) for (int i = x; i <= y; i++)
#define FOR1(i, x, y, z) for(int i = x; i <= y; i += z)
#define ROF(i, x, y) for (int i = x; i >= y; i--)
#define ROF1(i, x, y, z) for (int i = x; i >= y; i -= z)
#define uniq(x); sort(all(x)); x.resize(unique(all(x)) - x.begin());
#define mid ((tl + tr) >> 1)
#define LS v + v, tl, mid
#define RS v + v + 1, mid + 1, tr
//#define int ll

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class U> bool emin(T& a, const U& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template <class T, class U> bool emax(T& a, const U& b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b)
template <class T, class U> void erase(T& t, const U& u) { // don't erase
    auto it = t.find(u); //assert(it != end(t));
    if (it != t.end()) t.erase(it);
}

inline namespace FileIO {
	void setIn(string s)  { freopen(s.c_str(),"r",stdin); }
	void setOut(string s) { freopen(s.c_str(),"w",stdout); }
	void setIO(string s = "") {
		//cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
		ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
		// cin.exceptions(cin.failbit);
		// throws exception when do smth illegal
		// ex. try to read letter into int
		if (s.ss) setIn(s+".in"), setOut(s+".out"); // for old USACO
	}
}

int MOD = 1e9 + 33;
#ifndef int
struct Mint
{
    private:
        int normal(int x) { if (x >= MOD) x -= MOD; if (x < 0) x += MOD; return x;}
        int power(int x, int y) { int res = 1; for (;y;y >>= 1, x = (x * x) % MOD) if (y & 1) res = (res * x) % MOD; return res;}
    public:

        int x;
        Mint():x(0){}
        Mint(int y):x(normal(y)){}
        Mint operator -()const {return Mint(MOD - x);}
        Mint operator +(const Mint y) {return Mint(x + y.x);}
        Mint operator -(const Mint y) {return Mint(x - y.x);}
        Mint operator *(const Mint y) {return Mint(int((ll)x * y.x % MOD));}
        Mint operator *(const int y) {return Mint(int((ll)x * y % MOD));}
        Mint operator /(const Mint y) {return Mint(int((ll)x * power(y.x, MOD - 2) % MOD));}
        Mint &operator =(const Mint y) {x = normal(y.x); return *this;}
        Mint &operator +=(const Mint y) {x = normal(x + y.x); return *this;}
        Mint &operator -=(const Mint y) {x = normal(x - y.x); return *this;}
        Mint &operator *=(const Mint y) {x = int((ll)x * y.x % MOD); return *this;}
        Mint &operator *=(const int y) {x = int((ll)x * y % MOD); return *this;}
        Mint &operator /=(const Mint y) {x = int((ll)x * power(y.x, MOD - 2) % MOD); return *this;}
        bool operator ==(const int y) {return x == y;}
};
ostream& operator << (ostream& out, const Mint& x){ out << x.x; return out;}
#endif // int
template < typename T, typename TT > ostream& operator << (ostream& out, const pair < T, TT>& p) {out << p.fi << " " << p.se; return out;}
template < typename T, typename TT > pair < T, TT > operator + (const pair < T, TT >& p1, const pair < T, TT >& p2) {return make_pair(p1.fi + p2.fi, p1.se + p2.se);}
template < typename T, typename TT > pair < T, TT > operator += (pair < T, TT >& p1, const pair < T, TT>& p2) {p1.fi += p2.fi; p1.se += p2.se; return p1;}

int bp (int x, int y)
{
    ll res = 1;
    for (; y; y >>= 1, x = (x * x))
        if (y & 1) res = (res * x);
    return res;
}
ll bpm(ll x, ll y, ll md = MOD)
{
    ll res = 1;
    for (; y; y >>= 1, x = (x * x) % md)
        if (y & 1) res = (res * x) % md;
    return res;
}
/*
inline void normal(ll &x, int md = MOD)
{
    if (x < md && x >= 0) return;
    x %= md;
    if (x < 0) x += md;
}
inline int MUL(ll x, ll y, int md = MOD)
{
    normal(x, md); normal(y, md);
    return (x * y) % md;
}
inline int SQ(ll x, int md = MOD)
{
    normal(x, md);
    return MUL(x, x, md);
}
inline int ADD(int x, int y, int md = MOD)
{
    normal(x, md); normal(y, md);
    return (x + y >= md ? x + y - md : x + y);
}
inline int SUB(int x, int y, int md = MOD)
{
    normal(x, md); normal(y, md);
    x -= y;
    if (x < 0) x += md;
    return x;
}
inline int DIV(ll x, ll y, int md = MOD)
{
    normal(x, md); normal(y, md);
    y = bpm(y, md - 2, md);
    return MUL(x, y, md);
}*/

bool is_prime(int x)
{
    if (x <= 1) return 0;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return 0;
    return 1;
}

inline int cd(char c){return c - '0';}
inline char cc(int x){return x + '0';}
inline char cb(int x){return x + 'A';}
inline int cn(char c){return c - 'A';}
inline int diff(int x, int y){return abs(x - y);}
inline void abandon(){cout << "NO";exit(0);}
inline int rng(int l, int r){return (rnd() % (r - l + 1) + l);}
inline int pw2(int i){return (1 << i);}
inline bool bit(int mask, int i){return ((mask >> i) & 1);}
inline int lcm(int x, int y) {return (x / gcd(x, y)) * y;}
inline int sign(int x) {return (x < 0 ? -1 : !!x);}
inline void coutmask(int mask, int sz) {FOR (i, 0, sz - 1) cout << bit(mask, i);}

const ll INF = 1e15 + 7;
const int N = 1e5 + 40, T = 4 * N, logN = (int)log2(N) + 2, Nlog = N * logN * 2, basic = 41/*379999*/, inf = 1e9 + 7, Mod = 998244353, /*NWSE or ULDR*/sx[4] = {-1, 0, 1, 0}, sy[4] = {0, -1, 0, 1}, mod = 1e9 + 3;
const int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dy[8] = {1, 0, -1, 1, -1, 1, 0, -1}, sqN = (int)sqrt(N), BL = 316, BL2 = 1000;
const double eps = 1e-12, pi = acos(-1);

int n, m, r, l, e, id, mx = -inf, mn = inf, w, timer, tst, delta = 2e8 + 1;

unordered_map < ll, int > M;
vpii ans;
int X[N], Y[N], p[N];

int f;

ll get(int x, int y)
{
    x += delta;
    y += delta;
    return x * 1ll * inf + y;
}

pii unget(ll x)
{
    return {x / inf - delta, x % inf - delta};
}

void solve()
{
    ll x = 0, y = 0, z = 0;

    cin >> n;
    M.clear();
    FOR (i, 1, n + n)
    {
        cin >> X[i] >> Y[i];
        M[get(X[i], Y[i])]++;
        p[i] = i;
    }
    bool ok = 1;
    for (auto i : M)
    {
        if (i.se != 2) ok = 0;
    }
    shuffle(p + 1, p + n + n + 1, rnd);
    M.clear();
    ans.clear();
    if (ok)
    {
        cout << "1\n0 0\n";
        return;
    }
    if (n <= 100)
    {
        f = n + n;
        FOR (i, 1, n + n)
        {
            FOR (j, 1, n + n)
            {
                if (i == j) continue;
                M[get(X[p[j]] - X[p[i]], Y[p[j]] - Y[p[i]])]++;
                //M[get(X[p[i]] - X[p[j]], Y[p[i]] - Y[p[j]])]++;
            }
        }
        for (auto i : M) emax(mx, i.se);
        for (auto i : M)
        {
            //cout << unget(i.fi) << " " << i.se << endl;
            if (i.se == mx)
            {
                ans.pb(unget(i.fi));
            }
        }
        sort(all(ans));
        cout << ans.ss << endl;
        for (auto i : ans) cout << i << endl;
        return;
    }

    f = min(30, n + n);
    FOR (i, 1, f)
    {
        FOR (j, i + 1, n + n)
        {
            if (i == j) continue;
            M[get(X[p[j]] - X[p[i]], Y[p[j]] - Y[p[i]])]++;
            M[get(X[p[i]] - X[p[j]], Y[p[i]] - Y[p[j]])]++;
        }
    }
    mx = 0;
    for (auto i : M)
        emax(mx, i.se);
    for (auto i : M)
    {
        //cout << unget(i.fi) << " " << i.se << endl;
        if (i.se == mx)
        {
            ans.pb(unget(i.fi));
        }
    }
    sort(all(ans));
    cout << ans.ss << endl;
    for (auto i : ans) cout << i << endl;
}

signed main()
{
    int x, y, z;
    //setprecision(9);
    #ifdef LOCAL
    setIn("input.txt");
    setOut("output.txt");
    #else
    setIO();
    #endif

    int _ = 1;
    cin >> _;
    for (int i = 1; i <= _; ++i)
    {
        //cout << "Case " << i << ": ";
        solve();
        //cout << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10985ms
memory: 332108kb

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