Advertisement
Guest User

Untitled

a guest
Mar 30th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using std::cin;
  4. using std::cout;
  5. using std::cerr;
  6. using std::ios_base;
  7. using std::fixed;
  8. using std::endl;
  9.  
  10. using std::pair;
  11. using std::make_pair;
  12. using std::swap;
  13.  
  14. using std::string;
  15. using std::vector;
  16. using std::map;
  17. using std::set;
  18.  
  19. using std::sort;
  20. using std::reverse;
  21.  
  22. #define pb push_back
  23. #define mp make_pair
  24. #define all(x) x.begin(), x.end()
  25. #define rall(x) x.rbegin(), x.rend()
  26. #define sqr(x) ((x) * (x))
  27.  
  28. const int MAXN = 50005;
  29. const int INF = 1e9;
  30. const int MOD = 1e9+7;
  31. const long long L_INF = 4e18;
  32. const long double EPS = 1e-10;
  33. const long double PI = acos(-1.0);
  34.  
  35. struct Point {
  36. int x, y;
  37. int id;
  38. };
  39.  
  40. struct Edge {
  41. int v, u;
  42. double w;
  43. bool operator<(const Edge& other) const {
  44. return w < other.w - EPS;
  45. }
  46. };
  47.  
  48. std::mt19937 rnd(566);
  49. std::uniform_real_distribution<double> distr(0, PI);
  50.  
  51. int n;
  52. int x[MAXN], y[MAXN];
  53. Point line[MAXN];
  54. vector<Edge> g, mst;
  55. vector<pair<int, int> > nearest[MAXN];
  56. int par[MAXN];
  57.  
  58. int get(int v) {
  59. return v == par[v] ? v : par[v] = get(par[v]);
  60. }
  61.  
  62. bool join(int v, int u) {
  63. v = get(v), u = get(u);
  64. if (v == u)
  65. return 0;
  66. par[u] = v;
  67. return 1;
  68. }
  69.  
  70. int main() {
  71. ios_base::sync_with_stdio(false);
  72. cin.tie(nullptr);
  73. cout.precision(15);
  74. cout << fixed;
  75. srand(566);
  76.  
  77. cin >> n;
  78. for (int i = 0; i < n; i++) {
  79. cin >> x[i] >> y[i];
  80. line[i] = {x[i], y[i], i};
  81. par[i] = i;
  82. }
  83.  
  84. for (int k = 0; k < 20; k++) {
  85. double alpha = distr(rnd);
  86. double a = cos(alpha), b = sin(alpha);
  87. sort(line, line + n, [&](const Point& pt1, const Point& pt2) {
  88. return a * (pt1.x - pt2.x) + b * (pt1.y - pt2.y) < EPS;
  89. });
  90. for (int t = 1; t < 50; t++) {
  91. for (int i = 0; i < n - t; i++) {
  92. int v = line[i].id, u = line[i + t].id;
  93. int w = sqr(x[v] - x[u]) + sqr(y[v] - y[u]);
  94. nearest[v].pb(mp(w, u));
  95. nearest[u].pb(mp(w, v));
  96. }
  97. }
  98. for (int i = 0; i < n; i++) {
  99. sort(all(nearest[i]));
  100. int sz = unique(all(nearest[i])) - nearest[i].begin();
  101. nearest[i].resize(std::min(sz, 20));
  102. }
  103. }
  104.  
  105. for (int i = 0; i < n; i++)
  106. for (int j = 0; j < (int) nearest[i].size(); j++)
  107. g.pb({i, nearest[i][j].second, (double) nearest[i][j].first});
  108. sort(all(g));
  109.  
  110. double res = 0;
  111. for (auto& e : g) {
  112. //cerr << e.v << ' ' << e.u << ' ' << e.w << '\n';
  113. if (join(e.v, e.u)) {
  114. res += sqrt(e.w);
  115. mst.pb(e);
  116. }
  117. }
  118.  
  119. cout << res << '\n';
  120. for (auto& e : mst)
  121. cout << e.v + 1 << ' ' << e.u + 1 << '\n';
  122.  
  123. #ifdef LOCAL
  124. cerr << "\n== " << 1.0 * clock() / CLOCKS_PER_SEC << " sec.\n";
  125. #endif
  126. return 0;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement