Advertisement
ivnikkk

Untitled

Feb 8th, 2022
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.21 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. //#include "geometry.h"
  4. //#include "data_structure.h"
  5. using namespace std;
  6. using namespace chrono;
  7. #define all(a) a.begin(), a.end()
  8. #define allr(a) a.rbegin(), a.rend()
  9. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  10. typedef long long ll;
  11. typedef long double ld;
  12. const ld EPS = 1e-10;
  13.  
  14. #define Vec Point
  15.  
  16. int sign(ld x) {
  17.     if (x > EPS) return 1;
  18.     if (x < -EPS) return -1;
  19.     return 0;
  20. }
  21.  
  22. ld sq(ld x) {
  23.     return x * x;
  24. }
  25.  
  26. struct Point {
  27.     ld x, y;
  28.     Point() : x(0), y(0) {}
  29.     Point(ld _x, ld _y) : x(_x), y(_y) {}
  30.     Point operator-(const Point& other) const {
  31.         return Point(x - other.x, y - other.y);
  32.     }
  33.     Point operator+(const Point& other) const {
  34.         return Point(x + other.x, y + other.y);
  35.     }
  36.     Point operator*(const ld& other) const {
  37.         return Point(x * other, y * other);
  38.     }
  39.     // векторное произведение sin
  40.     ld operator^(const Point& other) const {
  41.         return x * other.y - y * other.x;
  42.     }
  43.     // скалярное произведение cos
  44.     ld operator*(const Point& other) const {
  45.         return x * other.x + y * other.y;
  46.     }
  47.     ld len2() const {
  48.         return sq(x) + sq(y);
  49.     }
  50.     ld len() const {
  51.         return sqrt(len2());
  52.     }
  53.     Point norm() const {
  54.         ld d = len();
  55.         return Point(x / d, y / d);
  56.     }
  57.     bool operator<(const Point& other) const {
  58.         if (sign(x - other.x) != 0) {
  59.             return x < other.x;
  60.         }
  61.         else if (sign(y - other.y) != 0) {
  62.             return y < other.y;
  63.         }
  64.         return false;
  65.     }
  66.     bool operator==(const Point& other) const {
  67.         return sign(x - other.x) == 0 && sign(y - other.y) == 0;
  68.     }
  69.     Point ort() {
  70.         return Point(-y, x);
  71.     }
  72.     void deb() const {
  73.         std::cerr << "(" << x << ", " << y << ")" << std::endl;
  74.     }
  75. };
  76.  
  77. struct Line {
  78.     ld a, b, c;
  79.     Line() : a(0), b(0), c(0) {}
  80.     Line(const Point& x, const Point& y) : a(y.y - x.y), b(x.x - y.x), c(x.y* y.x - y.y * x.x) {
  81.         ////// нормирование прямой
  82.         //ld d = Point(a, b).len();
  83.         //a /= d, b /= d, c /= d;
  84.         //if (sign(a) == -1) {
  85.         //  a = -a;
  86.         //  b = -b;
  87.         //  c = -c;
  88.         //}
  89.         //else if (sign(a) == 0 && sign(b) == 0) {
  90.         //  a = 0;
  91.         //  b = -b;
  92.         //  c = -b;
  93.         //}
  94.     }
  95.     bool operator==(const Line& other) const {
  96.         return sign(a - other.a) == 0 && sign(b - other.b) == 0 && sign(c-other.c)==0;
  97.     }
  98. };
  99. ld dist_points(Point a, Point b) {
  100.     return sqrtl(sq(a.x - b.x) + sq(a.y - b.y));
  101. }
  102. bool is_point_on_seg(const Point& a, const Point& b, const Point& x) {
  103.     return sign((a - b).len() - (a - x).len() - (b - x).len()) == 0;
  104. }
  105. ld dist_line(const Point& a, const Line& l) {
  106.     return abs(l.a * a.x + l.b * a.y + l.c) / sqrt(sq(l.a) + sq(l.b));
  107. }
  108. ld get_dist_line(Point& a, Point& c, Point& d) {
  109.     Line buf(c, d);
  110.     return dist_line(a, buf);
  111. }
  112. ld dist_point_segment(Point& x, Point& c, Point& d) {
  113.     Line check(c, d);
  114.     ld dis = dist_line(x, check);
  115.     Vec k(check.a, check.b);
  116.     k = k.norm() * dis;
  117.     Point suba = x + k;
  118.     Point subb = x - k;
  119.     if (is_point_on_seg(c, d, suba) || is_point_on_seg(c, d, subb)) {
  120.         return dis;
  121.     }
  122.     else {
  123.         return min(dist_points(x, c), dist_points(x, d));
  124.     }
  125. }
  126. bool line_cross(const Line& a, const Line& b, Point& ans) {
  127.     ld d = (a.b * b.a - a.a * b.b);
  128.     if (sign(d) == 0)
  129.         return false;
  130.     ans.x = (b.b * a.c - b.c * a.b) / d;
  131.     ans.y = (b.c * a.a - a.c * b.a) / d;
  132.     return true;
  133. }
  134. bool segment_cross(const Point& a, const Point& b, const Point& c, const Point& d) {
  135.     if (sign((a - b) ^ (c - d)) == 0) {
  136.         return is_point_on_seg(a, b, c) ||
  137.             is_point_on_seg(a, b, d) ||
  138.             is_point_on_seg(c, d, a) ||
  139.             is_point_on_seg(c, d, b);
  140.     }
  141.     Point ans;
  142.     if (line_cross(Line(a, b), Line(c, d), ans)) {
  143.         return is_point_on_seg(a, b, ans) && is_point_on_seg(c, d, ans);
  144.     }
  145. }
  146. ld dist_seg_to_seg(Point a, Point b, Point c, Point d) {
  147.     if (segment_cross(a, b, c, d)) {
  148.         return 0;
  149.     }
  150.     return min(min(dist_point_segment(a, c, d), dist_point_segment(b, c, d)), min(dist_point_segment(c, a, b), dist_point_segment(d, a, b)));
  151. }
  152. struct Polygon {
  153.     vector<Point> p;
  154. };
  155. signed main() {
  156. #ifdef _DEBUG
  157.     freopen("input.txt", "r", stdin);
  158.     freopen("output.txt", "w", stdout);
  159. #endif
  160.     srand(time(NULL));
  161.     ios_base::sync_with_stdio(false);
  162.     cin.tie(nullptr);
  163.     cout.tie(nullptr);
  164.     cout << fixed << setprecision(10);
  165.     ll n, a, b;
  166.     cin >> n >> a >> b;
  167.     vector<Polygon> mas(n);
  168.     for (ll i = 0; i < n; i++) {
  169.         Polygon& use = mas[i];
  170.         ll k;
  171.         cin >> k;
  172.         use.p.resize(k);
  173.         for (ll j = 0; j < k; j++) {
  174.             cin >> use.p[j].x >> use.p[j].y;
  175.         }
  176.     }
  177.     vector<vector<pair<ld,ll>>>gr(n);
  178.     for (ll i = 0; i < n; i++) {
  179.         Polygon& out = mas[i];
  180.         for (ll j = 0; j < n; j++) {
  181.             if (j == i)
  182.                 continue;
  183.             auto ter = [&](Point& from, Polygon& b,pair<Point,ll> &ans) {
  184.                 ll l = 0, r = b.p.size() - 1;
  185.                 while (r - l > 2) {
  186.                     ll ml = l + (r - l) / 3, mr = r - (r - l) / 3;
  187.                     if (dist_points(from, b.p[ml]) > dist_points(from, b.p[mr])) {
  188.                         l = ml;
  189.                     }
  190.                     else {
  191.                         r = mr;
  192.                     }
  193.                 }
  194.                 ll mid = (r + l) / 2;
  195.                 ld d1 = dist_points(from, b.p[l]), d2 = dist_points(from, b.p[r]), d3 = dist_points(from, b.p[mid]);
  196.                 ld mn = min(d1, min(d2, d3));
  197.                 if (sign(d1 - mn) == 0) {
  198.                     ans = { b.p[l],l };
  199.                 }
  200.                 else if (sign(d2 - mn) == 0) {
  201.                     ans = { b.p[r],r };
  202.                 }
  203.                 else {
  204.                     ans = { b.p[mid],mid };
  205.                 }
  206.                 return mn;
  207.             };
  208.             Polygon& in = mas[j];
  209.             ll l = 0, r = out.p.size() - 1;
  210.             pair<Point,ll> ans2={in.p[0],0};
  211.             while (r - l > 2) {
  212.                 ll ml = l + (r - l) / 3, mr = r - (r - l) / 3;
  213.                 if (ter(out.p[ml],in,ans2) > ter(out.p[mr],in,ans2)) {
  214.                     l = ml;
  215.                 }
  216.                 else {
  217.                     r = mr;
  218.                 }
  219.             }
  220.             pair<Point,ll> ans1;
  221.             ll mid = (r + l) / 2;
  222.             ld d1 = dist_points(ans2.first, out.p[l]), d2 = dist_points(ans2.first, out.p[r]),d3 = dist_points(ans2.first,out.p[mid]);
  223.             ld mn = min(d1, min(d2, d3));
  224.             if (sign(d1 - mn) == 0) {
  225.                 ans1 = { out.p[l],l };
  226.             }
  227.             else if (sign(d2 - mn) == 0) {
  228.                 ans1 = { out.p[r],r };
  229.             }
  230.             else {
  231.                 ans1 = { out.p[mid],mid };
  232.             }
  233.             //out.p[ans1.second + 1 < out.p.size() ? ans1.second + 1 : 0]
  234.             ll ind_seg1_1 = ans1.second - 1 >= 0 ? ans1.second - 1 : out.p.size() - 1;
  235.             ll ind_seg1_2 = ans1.second + 1 < out.p.size() ? ans1.second + 1 : 0;
  236.             ll ind_seg_2_1 = ans2.second - 1 >= 0 ? ans2.second - 1 : in.p.size() - 1;
  237.             ll ind_seg_2_2 = ans2.second + 1 < in.p.size() ? ans2.second + 1 : 0;
  238.             ld dist1 = min(dist_seg_to_seg(out.p[ind_seg1_1], ans1.first, in.p[ind_seg_2_1], ans2.first), dist_seg_to_seg(out.p[ind_seg1_1], ans1.first, ans2.first, in.p[ind_seg_2_2]));
  239.             ld dist2 = min(dist_seg_to_seg(ans1.first, out.p[ind_seg1_2], in.p[ind_seg_2_1], ans2.first), dist_seg_to_seg(out.p[ind_seg1_1], ans1.first, ans2.first, in.p[ind_seg_2_2]));
  240.             gr[i].push_back({ min(dist1,dist2),j});
  241.         }
  242.     }
  243.     const ld inf = 1e18;
  244.     vector<ld> dist(n, inf);
  245.     a--, b--;
  246.     dist[a] = 0;
  247.     set < pair<ld, ll> > queue;
  248.     queue.insert({ dist[a], a });
  249.     while (!queue.empty()) {
  250.         ll v = queue.begin()->second;
  251.         queue.erase(queue.begin());
  252.         for (ll j = 0; j < gr[v].size(); ++j) {
  253.             ll u = gr[v][j].second;
  254.             ld w = gr[v][j].first;
  255.             if (dist[v] + w < dist[u]) {
  256.                 queue.erase({ dist[u], u });
  257.                 dist[u] = dist[v] + w;
  258.                 queue.insert({ dist[u], u });
  259.             }
  260.         }
  261.     }
  262.     cout << dist[b] << endl;
  263. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement