Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef double d;
- struct circle {
- d x, y, r;
- };
- d dist(d x1, d y1, d x2, d y2) {
- d dx = x2 - x1, dy = y2 - y1;
- return sqrt(dx * dx + dy * dy);
- }
- bool inside(const circle &circ, d x, d y) {
- return dist(circ.x, circ.y, x, y) <= circ.r + 1e-9;
- }
- d len(d ax, d ay, d bx, d by, const circle &circ) {
- d l = dist(ax, ay, bx, by);
- if (l < 1e-9) return 0.0;
- d t = ((circ.x - ax) * (bx - ax) + (circ.y - ay) * (by - ay)) / (l * l);
- t = max((d)0.0, min((d)1.0, t));
- d cx = ax + t * (bx - ax), cy = ay + t * (by - ay);
- d d_from_center = dist(circ.x, circ.y, cx, cy);
- if (d_from_center > circ.r + 1e-9) return 0.0;
- d half = sqrt(circ.r * circ.r - d_from_center * d_from_center);
- d t1 = t - half / l, t2 = t + half / l;
- t1 = max((d)0.0, t1), t2 = min((d)1.0, t2);
- return (t2 - t1) * l;
- }
- struct union_find {
- vector<int> parent;
- union_find(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
- int find(int a) {
- if (parent[a] != a) parent[a] = find(parent[a]);
- return parent[a];
- }
- void join(int a, int b) {
- a = find(a), b = find(b);
- if (a != b) parent[a] = b;
- }
- };
- int minDistance(vector<int> &a, vector<int> &b, vector<vector<int>> &lights) {
- d ax = a[0], ay = a[1], bx = b[0], by = b[1];
- int n = lights.size();
- vector<circle> circles(n);
- for (int i = 0; i < n; ++i) {
- circles[i] = {lights[i][0], lights[i][1], lights[i][2]};
- }
- vector<int> a_inside, b_inside;
- for (int i = 0; i < n; ++i) {
- if (inside(circles[i], ax, ay)) a_inside.push_back(i);
- if (inside(circles[i], bx, by)) b_inside.push_back(i);
- }
- if (!a_inside.empty() && !b_inside.empty()) {
- union_find uf(n);
- for (int i = 0; i < n; ++i) {
- for (int j = i + 1; j < n; ++j) {
- if (dist(circles[i].x, circles[i].y, circles[j].x, circles[j].y) <= circles[i].r + circles[j].r + 1e-9) {
- uf.join(i, j);
- }
- }
- }
- for (int i : a_inside) {
- for (int j : b_inside) {
- if (uf.find(i) == uf.find(j)) {
- return 0;
- }
- }
- }
- }
- int s = 0, e = 1, base = 2, tot = base + n;
- vector<d> dists(tot, 1e18);
- dists[s] = 0.0;
- priority_queue<pair<d, int>, vector<pair<d, int>>, greater<pair<d, int>>> q; // Changed auto to explicit type
- q.push(make_pair(0.0, s)); // Changed to make_pair for C++14 compatibility
- while (!q.empty()) {
- pair<d, int> top = q.top(); // Changed auto to explicit type
- q.pop();
- d cur = top.first;
- int u = top.second;
- if (cur > dists[u] + 1e-9) continue;
- if (u == s) {
- for (int i = 0; i < n; ++i) {
- d edge = max((d)0.0, dist(ax, ay, circles[i].x, circles[i].y) - circles[i].r);
- int v = base + i;
- if (dists[v] > cur + edge) {
- dists[v] = cur + edge;
- q.push(make_pair(dists[v], v)); // Changed to make_pair
- }
- }
- d ab = dist(ax, ay, bx, by), mx = 0.0;
- for (auto &circ : circles) mx = max(mx, len(ax, ay, bx, by, circ));
- d edge = max(ab - mx, (d)0.0);
- if (dists[e] > cur + edge) {
- dists[e] = cur + edge;
- q.push(make_pair(dists[e], e)); // Changed to make_pair
- }
- } else if (u == e) {
- continue;
- } else {
- int ci = u - base;
- d edge = max((d)0.0, dist(circles[ci].x, circles[ci].y, bx, by) - circles[ci].r);
- if (dists[e] > cur + edge) {
- dists[e] = cur + edge;
- q.push(make_pair(dists[e], e)); // Changed to make_pair
- }
- for (int j = 0; j < n; ++j) {
- if (j == ci) continue;
- d dij = dist(circles[ci].x, circles[ci].y, circles[j].x, circles[j].y);
- d edge = max((d)0.0, dij - circles[ci].r - circles[j].r);
- if (dij <= circles[ci].r + circles[j].r + 1e-9) edge = 0.0;
- int v = base + j;
- if (dists[v] > cur + edge) {
- dists[v] = cur + edge;
- q.push(make_pair(dists[v], v)); // Changed to make_pair
- }
- }
- }
- }
- return (int)floor(dists[e]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
