Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using std::cin;
- using std::cout;
- using std::cerr;
- using std::ios_base;
- using std::fixed;
- using std::endl;
- using std::pair;
- using std::make_pair;
- using std::swap;
- using std::string;
- using std::vector;
- using std::map;
- using std::set;
- using std::sort;
- using std::reverse;
- #define pb push_back
- #define mp make_pair
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define sqr(x) ((x) * (x))
- const int MAXN = 50005;
- const int INF = 1e9;
- const int MOD = 1e9+7;
- const long long L_INF = 4e18;
- const long double EPS = 1e-10;
- const long double PI = acos(-1.0);
- struct Point {
- int x, y;
- int id;
- };
- struct Edge {
- int v, u;
- double w;
- bool operator<(const Edge& other) const {
- return w < other.w - EPS;
- }
- };
- std::mt19937 rnd(566);
- std::uniform_real_distribution<double> distr(0, PI);
- int n;
- int x[MAXN], y[MAXN];
- Point line[MAXN];
- vector<Edge> g, mst;
- vector<pair<int, int> > nearest[MAXN];
- int par[MAXN];
- int get(int v) {
- return v == par[v] ? v : par[v] = get(par[v]);
- }
- bool join(int v, int u) {
- v = get(v), u = get(u);
- if (v == u)
- return 0;
- par[u] = v;
- return 1;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.precision(15);
- cout << fixed;
- srand(566);
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> x[i] >> y[i];
- line[i] = {x[i], y[i], i};
- par[i] = i;
- }
- for (int k = 0; k < 20; k++) {
- double alpha = distr(rnd);
- double a = cos(alpha), b = sin(alpha);
- sort(line, line + n, [&](const Point& pt1, const Point& pt2) {
- return a * (pt1.x - pt2.x) + b * (pt1.y - pt2.y) < EPS;
- });
- for (int t = 1; t < 50; t++) {
- for (int i = 0; i < n - t; i++) {
- int v = line[i].id, u = line[i + t].id;
- int w = sqr(x[v] - x[u]) + sqr(y[v] - y[u]);
- nearest[v].pb(mp(w, u));
- nearest[u].pb(mp(w, v));
- }
- }
- for (int i = 0; i < n; i++) {
- sort(all(nearest[i]));
- int sz = unique(all(nearest[i])) - nearest[i].begin();
- nearest[i].resize(std::min(sz, 20));
- }
- }
- for (int i = 0; i < n; i++)
- for (int j = 0; j < (int) nearest[i].size(); j++)
- g.pb({i, nearest[i][j].second, (double) nearest[i][j].first});
- sort(all(g));
- double res = 0;
- for (auto& e : g) {
- //cerr << e.v << ' ' << e.u << ' ' << e.w << '\n';
- if (join(e.v, e.u)) {
- res += sqrt(e.w);
- mst.pb(e);
- }
- }
- cout << res << '\n';
- for (auto& e : mst)
- cout << e.v + 1 << ' ' << e.u + 1 << '\n';
- #ifdef LOCAL
- cerr << "\n== " << 1.0 * clock() / CLOCKS_PER_SEC << " sec.\n";
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement