Derga

Untitled

Jun 25th, 2024
640
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iomanip>
  3. #include <iostream>
  4. #include <map>
  5. #include <set>
  6. #include <string>
  7. #include <queue>
  8. #include <tuple>
  9. #include <vector>
  10.  
  11. using namespace std;
  12.  
  13. const int START_COLOR = 0;
  14. const int COLOR1 = 1;
  15. const int COLOR2 = -1;
  16.  
  17. void Dfs(int idx, const vector<int>& x_coords, const vector<int>& y_coords, int dist,
  18.     vector<int>& colors, bool& is_bipartite, int color)
  19. {
  20.     colors[idx] = COLOR1;
  21.  
  22.     for (int i = 0; i < idx; ++i) {
  23.         if (i == idx) continue;
  24.         if ((x_coords[i] - x_coords[idx]) * (x_coords[i] - x_coords[idx]) +
  25.             (y_coords[i] - y_coords[idx]) * (y_coords[i] - y_coords[idx]) > dist) continue;
  26.         if (colors[i] == START_COLOR) {
  27.             Dfs(i, x_coords, y_coords, dist, colors, is_bipartite, -color);
  28.         } else if (colors[i] != -color) {
  29.             is_bipartite = false;
  30.             return;
  31.         }
  32.     }
  33. }
  34.  
  35. bool IsBipartite(const vector<int>& x_coords, const vector<int>& y_coords, int dist) {
  36.     vector<int> colors(x_coords.size(), START_COLOR);
  37.     bool is_bipartite = true;
  38.     for (int i = 0; i < x_coords.size(); ++i) {
  39.         if (colors[i] != START_COLOR) continue;
  40.  
  41.         Dfs(i, x_coords, y_coords, dist, colors, is_bipartite, COLOR1);
  42.     }
  43.     return is_bipartite;
  44. }
  45.  
  46. int main() {
  47.     int stations_count;
  48.     cin >> stations_count;
  49.     vector<int> x_coords(stations_count);
  50.     vector<int> y_coords(stations_count);
  51.     for (int i = 0; i < stations_count; ++i) {
  52.         cin >> x_coords[i] >> y_coords[i];
  53.     }
  54.  
  55.     int64_t l = 0;
  56.     int64_t r = 2 * (10'000 + 10'000) * (10'000 + 10'000) + 1;
  57.     while (l + 1 < r) {
  58.         int64_t m = (l + r) / 2;
  59.         if (IsBipartite(x_coords, y_coords, m)) l = m;
  60.         else r = m;
  61.     }
  62.  
  63.     cout << fixed << setprecision(8) << sqrt(l) / 2;
  64.  
  65.     return 0;
  66. }
  67. /*
  68. test1
  69. 4
  70. 0 0
  71. 0 1
  72. 1 0
  73. 1 1
  74.  
  75. 0.70710678118654752
  76. 1 2 2 1
  77. */
Advertisement
Add Comment
Please, Sign In to add comment