Advertisement
Andre1314

Untitled

Oct 11th, 2023
940
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 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. // R - радіус вазона, з яким ми хочемо пройти
  33. bool canFit(pll firstP, pll secondP, ld R) {
  34.     return sqrt(pow(secondP.first - firstP.first, 2) + pow(secondP.second - firstP.second, 2)) - 2 * r > R * 2;
  35. }
  36.  
  37. // тут ми проходимося по колонам і дивимося де ми не можемо пройти між колонами або стінами
  38. // і будуємо граф з тих колон між якими не можна пройти
  39. bool checkGraph(ld R, ll s, ll e) {
  40.     Graph g(n + 2);
  41.     for (int i = 0; i < n; i++) {
  42.         for (int j = 0; j < n; j++) {
  43.             if (i != j && !canFit(pillars[i], pillars[j], R)) {
  44.                 g.addEdge(i, j);
  45.             }
  46.         }
  47.  
  48.         if (pillars[i].first - r - xl <= R * 2) {
  49.             g.addEdge(i, n);
  50.             g.addEdge(n, i);
  51.         }
  52.  
  53.         if (pillars[i].first + r + R * 2 >= xr) {
  54.             g.addEdge(i, n + 1);
  55.             g.addEdge(n + 1, i);
  56.         }
  57.     }
  58.  
  59.     //перевіряємо чи є шлях від лівої до правої стіни
  60.  
  61.     vector<bool> used(g.adj.size());
  62.     queue<ll> q;
  63.     used[s] = true;
  64.     q.push(s);
  65.  
  66.     while (!q.empty()) {
  67.         ll cur = q.front();
  68.         q.pop();
  69.  
  70.         for (ll i : g.adj[cur]) {
  71.             if (!used[i]) {
  72.                 q.push(i);
  73.                 used[i] = true;
  74.                 if (i == e) return true;
  75.             }
  76.         }
  77.     }
  78.  
  79.     return false;
  80. }
  81.  
  82. //бінарним пошуком ми просто перебираємо який радіус нам підійде для того аби пройти
  83. ld binSrch() {
  84.     ld lt = 0;
  85.     ld rt = abs(xr) + abs(xl);
  86.  
  87.     while (rt - lt > eps) {
  88.         ld m = (rt + lt) / 2;
  89.         bool smaller = checkGraph(m, n, n + 1);
  90.  
  91.         if (smaller) rt = m;
  92.         else lt = m;
  93.     }
  94.  
  95.     return lt;
  96. }
  97.  
  98. int main()
  99. {
  100.     cin >> xl >> xr; // координати лівої та правої стін коридору
  101.     cin >> r; // радіус колон у коридорі
  102.     cin >> n; // кількість колон
  103.  
  104.     pillars.resize(n);
  105.  
  106.     for (int i = 0; i < n; i++) {
  107.         cin >> xi >> yi;
  108.         pillars[i].first = xi;
  109.         pillars[i].second = yi;
  110.     }
  111.  
  112.     cout << binSrch() * 2;
  113.  
  114.     return 0;
  115. }
  116.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement