SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. /*
  3.  
  4.  
  5.                           |~~~~~~~|
  6.                           |       |
  7.                           |       |
  8.                           |       |
  9.                           |       |
  10.                           |       |
  11. |~.\\\_\~~~~~~~~~~~~~~xx~~~         ~~~~~~~~~~~~~~~~~~~~~/_//;~|
  12. |  \  o \_         ,XXXXX),    иисус                _..-~ o /  |
  13. |    ~~\  ~-.     XXXXX`)))),                 _.--~~   .-~~~   |
  14. ~~~~~~~`\   ~\~~~XXX' _/ ';))     |~~~~~~..-~     _.-~ ~~~~~~~
  15.          `\   ~~--`_\~\, ;;;\)__.---.~~~      _.-~
  16.            ~-.       `:;;/;; \          _..-~~
  17.               ~-._      `''        /-~-~
  18.                   `\            /  /
  19.                     |         ,   | |
  20.                      |  '        /  |
  21.                       \/;           |
  22.                        ;;           |
  23.                        `;   .       |
  24.                        |~~~-----.....|
  25.                       | \             \
  26.                      | /\~~--...__    |
  27.                      (|  `\       __-\|
  28.                      ||    \_   /~    |
  29.                      |)     \~-'      |
  30.                       |      | \      '
  31.                       |      |  \    :
  32.                        \     |  |    |
  33.                         |    )  (    )
  34.                          \  /;  /\  |
  35.                          |    |/   |
  36.                          |    |   |
  37.                           \  .'  ||
  38.                           |  |  | |
  39.                           (  | |  |
  40.                           |   \ \ |
  41.                           || o `.)|
  42.                           |`\\\\) |
  43.                           |       |
  44.                           |       |
  45.                           |       |
  46. */
  47.  
  48.  
  49. #include <bits/stdc++.h>
  50.  
  51. #pragma GCC optimize("Ofast")
  52. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
  53. #pragma GCC optimize ("unroll-loops")
  54.  
  55. using namespace std;
  56.  
  57. #define TASK "tree"
  58.  
  59. typedef unsigned short int ll;
  60. typedef long double ld;
  61. typedef pair<ll, ll> par;
  62. typedef unsigned int ui;
  63.  
  64. #define all(x) (x).begin(), (x).end()
  65. #define rall(x) (x).rbegin(), (x).rend()
  66. #define X first
  67. #define Y second
  68. #define pw(x) (1ll << (x))
  69. #define _ inline
  70.  
  71. ll rnd() { return (rand() << 16) + rand(); }
  72.  
  73. ll p[50001], r[50001];
  74.  
  75. _ ll findP(ll x) { return (p[x] == x ? x : p[x] = findP(p[x]));}
  76.  
  77. _ void Merge(ll a, ll b) {
  78.     a = findP(a), b = findP(b);
  79.     if (a == b) return;
  80.     if (r[a] < r[b]) swap(a, b);
  81.     if (r[a] == r[b]) r[a]++;
  82.     p[b] = a;
  83. }
  84.  
  85. struct edge {
  86.     ll v, to;
  87.     int w;
  88.     edge() {}
  89.     edge(ll v, ll to, int w) : v(v), to(to), w(w) {}
  90. };
  91.  
  92. bool operator < (edge a, edge b) {
  93.     return a.w < b.w;
  94. }
  95.  
  96. ll C = 650;
  97.  
  98. _ int f(par a, par b) {
  99.     return (a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y);
  100. }
  101.  
  102. par q[50001];
  103.  
  104. pair<par, ll> a[50001];
  105.  
  106. _ int source() {
  107.     ll n;
  108.     cin >> n;
  109.     bool flag = (n >= 21000);
  110.     for (int i = 0; i < n; ++i) {
  111.         p[i] = i;
  112.         r[i] = 0;
  113.     }
  114.     for (int i = 0; i < n; ++i) {
  115.         cin >> a[i].X.Y >> a[i].X.X;
  116.         a[i].Y = i;
  117.     }
  118.     sort(a, a + n);
  119.     vector<edge> e;
  120.     e.reserve(50001 * C);
  121.     for (int i = 0; i < n; ++i) {
  122.         for (int j = 0; j < C; ++j) {
  123.             if (i + j == n) break;
  124.             int w = f(a[i].X, a[i + j].X);
  125.             if (flag && w >= 10000) continue;
  126.             e.push_back(edge(i, i + j, w));
  127.         }
  128.     }
  129.     sort(all(e));
  130.     ld ans = 0;
  131.     ll sizeq = 0;
  132.     for (int i = 0; i < e.size(); ++i) {
  133.         edge cur = e[i];
  134.         ll v1 = cur.v, to1 = cur.to;
  135.         ll v = findP(cur.v), to = findP(cur.to);
  136.         if (v == to) continue;
  137.         Merge(v, to);
  138.         q[sizeq++] = {v1, to1};
  139.         ans += sqrt(cur.w);
  140.     }
  141.     cout << fixed << setprecision(15) << ans << '\n';
  142.     for (int i = 0; i < sizeq; ++i) {
  143.         cout << a[q[i].X].Y + 1 << ' ' << a[q[i].Y].Y + 1 << '\n';
  144.     }
  145.     return 0;
  146. }
  147.  
  148. int main() {
  149. #ifdef aokigahara
  150.     assert(freopen("input.txt", "r", stdin));
  151.     assert(freopen("output.txt", "w", stdout));
  152. #else
  153.     //freopen(TASK".in", "r", stdin);
  154.     //freopen(TASK".out", "w", stdout);
  155. #endif
  156.  
  157.     srand(time(NULL));
  158.     ios::sync_with_stdio(0);
  159.     cin.tie(0);
  160.     cout.tie(0);
  161.  
  162.         source();
  163.  
  164. #ifdef aokigahara
  165.     cerr << "TIME :: " << clock() * 1.0 / CLOCKS_PER_SEC;
  166. #endif
  167.     return 0;
  168. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top