fork download
copy 
  1. /*
  2. QUESTION 6: Walking Through Illuminated Regions
  3.  
  4. Problem Statement:
  5. You are given N lamps on a 2D plane.
  6.  
  7. Each lamp lights a circular region.
  8.  
  9. You are given:
  10. - center of every lamp
  11. - radius of every lamp
  12. - start point
  13. - end point
  14.  
  15. You can walk only inside lit areas.
  16. You may move from one lamp region to another if the two circles overlap or touch.
  17.  
  18. Return whether it is possible to travel from start to end without stepping into darkness.
  19.  
  20. Hard Constraints:
  21. 1 <= N <= 1000
  22. Coordinates may be decimal.
  23. -1e6 <= coordinate values <= 1e6
  24. 1 <= radius <= 1e6
  25.  
  26. Example:
  27. lamps:
  28. 1. center = (0, 0), radius = 2
  29. 2. center = (3, 0), radius = 2
  30. 3. center = (7, 0), radius = 1
  31.  
  32. start = (0, 1)
  33. end = (7, 0)
  34.  
  35. Expected Output:
  36. false
  37.  
  38. Explanation:
  39. The first two circles overlap.
  40. The third circle is separated.
  41. So the start and end are not in the same connected lit region.
  42.  
  43. Brute Force:
  44. Start from all lamps containing the start point.
  45. DFS through overlapping lamps.
  46. If any visited lamp contains the end point, return true.
  47.  
  48. Time Complexity:
  49. O(N^2)
  50.  
  51. Optimized Approach:
  52. Treat each lamp as a graph node.
  53.  
  54. Connect two lamps if:
  55. distance between centers <= r1 + r2
  56.  
  57. Also connect:
  58. start point to every lamp containing it
  59. end point to every lamp containing it
  60.  
  61. Use DSU to check if start and end belong to the same component.
  62.  
  63. Time Complexity:
  64. O(N^2)
  65.  
  66. Space Complexity:
  67. O(N)
  68. */
  69.  
  70. #include <bits/stdc++.h>
  71. using namespace std;
  72.  
  73. class Solution {
  74. public:
  75.     struct DSU {
  76.         vector<int> parent, size;
  77.  
  78.         DSU(int n) {
  79.             parent.resize(n);
  80.             size.assign(n, 1);
  81.             iota(parent.begin(), parent.end(), 0);
  82.         }
  83.  
  84.         int find(int x) {
  85.             if (parent[x] == x) return x;
  86.             return parent[x] = find(parent[x]);
  87.         }
  88.  
  89.         void unite(int a, int b) {
  90.             a = find(a);
  91.             b = find(b);
  92.  
  93.             if (a == b) return;
  94.  
  95.             if (size[a] < size[b]) swap(a, b);
  96.  
  97.             parent[b] = a;
  98.             size[a] += size[b];
  99.         }
  100.     };
  101.  
  102.     struct Lamp {
  103.         long double x, y, r;
  104.     };
  105.  
  106.     bool inside(long double px, long double py, const Lamp& c) {
  107.         long double dx = px - c.x;
  108.         long double dy = py - c.y;
  109.  
  110.         return dx * dx + dy * dy <= c.r * c.r + 1e-12L;
  111.     }
  112.  
  113.     bool overlap(const Lamp& a, const Lamp& b) {
  114.         long double dx = a.x - b.x;
  115.         long double dy = a.y - b.y;
  116.  
  117.         long double sumR = a.r + b.r;
  118.  
  119.         return dx * dx + dy * dy <= sumR * sumR + 1e-12L;
  120.     }
  121.  
  122.     bool canWalk(vector<vector<long double>>& data,
  123.                  long double xs,
  124.                  long double ys,
  125.                  long double xt,
  126.                  long double yt) {
  127.  
  128.         int n = data.size();
  129.  
  130.         vector<Lamp> lamps(n);
  131.  
  132.         for (int i = 0; i < n; i++) {
  133.             lamps[i] = {data[i][0], data[i][1], data[i][2]};
  134.         }
  135.  
  136.         int START = n;
  137.         int END = n + 1;
  138.  
  139.         DSU dsu(n + 2);
  140.  
  141.         for (int i = 0; i < n; i++) {
  142.             if (inside(xs, ys, lamps[i])) dsu.unite(START, i);
  143.             if (inside(xt, yt, lamps[i])) dsu.unite(END, i);
  144.         }
  145.  
  146.         for (int i = 0; i < n; i++) {
  147.             for (int j = i + 1; j < n; j++) {
  148.                 if (overlap(lamps[i], lamps[j])) {
  149.                     dsu.unite(i, j);
  150.                 }
  151.             }
  152.         }
  153.  
  154.         return dsu.find(START) == dsu.find(END);
  155.     }
  156. };
  157.  
  158. int main() {
  159.     Solution sol;
  160.  
  161.     vector<vector<long double>> lamps = {
  162.         {0, 0, 2},
  163.         {3, 0, 2},
  164.         {7, 0, 1}
  165.     };
  166.  
  167.     bool ans = sol.canWalk(lamps, 0, 1, 7, 0);
  168.  
  169.     cout << (ans ? "true" : "false") << endl;
  170.  
  171.     return 0;
  172. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
false
https://ideone.com/nJ9TZh
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!