結果

問題 No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
コンテスト
ユーザー shobonvip
提出日時 2024-02-23 22:27:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 661 ms / 2,000 ms
コード長 3,947 bytes
コンパイル時間 4,903 ms
コンパイル使用メモリ 273,996 KB
最終ジャッジ日時 2025-02-19 20:14:41
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

// https://judge.yosupo.jp/submission/117923
struct UnionFind {
    vector<int> par;
    vector<int> siz;
    vector<int> edg;

    UnionFind(int N) : par(N), siz(N), edg(N) {
        for(int i = 0; i < N; ++i){
            par[i] = i;
            siz[i] = 1;
            edg[i] = 0;
        }
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry){
            edg[rx]++;
            return;
        }
        par[rx] = ry;
        siz[ry] += siz[rx];
        edg[ry] += edg[rx] + 1;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return siz[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};
template <typename T>
vector<pair<int, int>> manhattanMST(vector<T> x, vector<T> y){
    int n = x.size();
    vector<tuple<T, int, int>> edge;
    edge.reserve(4 * n);
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    for(int s = 0; s < 2; ++s){
        for(int t = 0; t < 2; ++t){
            sort(idx.begin(), idx.end(), [&](const int i, const int j) {
                return x[i] + y[i] < x[j] + y[j];
            });
            map<T, int, greater<>> map;
            for(const int i : idx){
                for(auto iter = map.lower_bound(y[i]); iter != map.end(); iter = map.erase(iter)){
                    const int j = iter->second;
                    const T dx = x[i] - x[j];
                    const T dy = y[i] - y[j];
                    if(dy > dx) break;
                    edge.emplace_back(dx + dy, i, j);
                }
                map[y[i]] = i;
            }
            swap(x, y);
        }
        for(int i = 0; i < n; ++i) {
            x[i] *= -1;
        }
    }
    sort(edge.begin(), edge.end());
    UnionFind dsu(n);
    vector<pair<int, int>> used;
    used.reserve(n - 1);
    for(const auto& [c, i, j] : edge){
        if(!dsu.same(i, j)){
            used.emplace_back(i, j);
            dsu.unite(i, j);
        }
    }
    return used;
}
// -------

void solve(){
	int n;
	ll l; cin >> n >> l;
	vector<int> x(n), y(n);
	rep(i,0,n){
		cin >> x[i] >> y[i];
	}
	vector<pair<int,int>> mst = manhattanMST(x, y);
	
	vector ikeru(n, vector<int>(0));
	for (auto [i, j]: mst){
		ikeru[i].push_back(j);
		ikeru[j].push_back(i);
	}

	vector<int> ans;
	auto dfs = [&](auto self, int i, int p) -> void {
		ans.push_back(i);
		for (int j: ikeru[i]){
			if (j == p) continue;
			self(self, j, i);
			ans.push_back(i);
		}
	};

	dfs(dfs,0,-1);

	cout << (int)ans.size() << '\n';
	rep(i,0,(int)ans.size()){
		cout << x[ans[i]] << ' ' << y[ans[i]] << '\n';
	}
}

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