Advertisement
Andre1314

Untitled

Nov 8th, 2023
477
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <queue>
  6. #include <math.h>
  7.  
  8. #define ll long long
  9. #define ld long double
  10. #define pll pair<ll, ll>
  11.  
  12. using namespace std;
  13.  
  14. const double eps = 0.0001;
  15.  
  16. ll xl, xr, r, n, xi, yi;
  17. vector<pll> pillars;
  18.  
  19. class Graph {
  20. public:
  21.     vector<vector<ll>> adj;
  22.    
  23.     Graph(int v) {
  24.         adj.resize(v);
  25.     }
  26.  
  27.     void addEdge(int u, int w) {
  28.         adj[u].push_back(w);
  29.     }
  30. };
  31.  
  32. bool canFit(pll firstP, pll secondP, ld R) {
  33.     return sqrt(pow(secondP.first - firstP.first, 2) + pow(secondP.second - firstP.second, 2)) - 2 * r > R * 2;
  34. }
  35.  
  36. bool checkGraph(ld R, ll s, ll e) {
  37.     Graph g(n + 2);
  38.     for (int i = 0; i < n; i++) {
  39.         for (int j = 0; j < n; j++) {
  40.             if (i != j && !canFit(pillars[i], pillars[j], R)) {
  41.                 g.addEdge(i, j);
  42.             }
  43.         }
  44.  
  45.         if (pillars[i].first - r - xl <= R * 2) {
  46.             g.addEdge(i, n);
  47.             g.addEdge(n, i);
  48.         }
  49.  
  50.         if (pillars[i].first + r + R * 2 >= xr) {
  51.             g.addEdge(i, n + 1);
  52.             g.addEdge(n + 1, i);
  53.         }
  54.     }
  55.  
  56.     vector<bool> used(g.adj.size());
  57.     queue<ll> q;
  58.     used[s] = true;
  59.     q.push(s);
  60.  
  61.     while (!q.empty()) {
  62.         ll cur = q.front();
  63.         q.pop();
  64.  
  65.         for (ll i : g.adj[cur]) {
  66.             if (!used[i]) {
  67.                 q.push(i);
  68.                 used[i] = true;
  69.                 if (i == e) return true;
  70.             }
  71.         }
  72.     }
  73.  
  74.     return false;
  75. }
  76.  
  77. ld binSrch() {
  78.     ld lt = 0;
  79.     ld rt = abs(xr) + abs(xl);
  80.  
  81.     while (rt - lt > eps) {
  82.         ld m = (rt + lt) / 2;
  83.         bool smaller = checkGraph(m, n, n + 1);
  84.  
  85.         if (smaller) rt = m;
  86.         else lt = m;
  87.     }
  88.  
  89.     return lt;
  90. }
  91.  
  92. int main()
  93. {
  94.     cin >> xl >> xr;
  95.     cin >> r;
  96.     cin >> n;
  97.  
  98.     pillars.resize(n);
  99.  
  100.     for (int i = 0; i < n; i++) {
  101.         cin >> xi >> yi;
  102.         pillars[i].first = xi;
  103.         pillars[i].second = yi;
  104.     }
  105.  
  106.     cout << binSrch() * 2;
  107.  
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement