Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- //#include "geometry.h"
- //#include "data_structure.h"
- using namespace std;
- using namespace chrono;
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef long double ld;
- const ld EPS = 1e-10;
- #define Vec Point
- int sign(ld x) {
- if (x > EPS) return 1;
- if (x < -EPS) return -1;
- return 0;
- }
- ld sq(ld x) {
- return x * x;
- }
- struct Point {
- ld x, y;
- Point() : x(0), y(0) {}
- Point(ld _x, ld _y) : x(_x), y(_y) {}
- Point operator-(const Point& other) const {
- return Point(x - other.x, y - other.y);
- }
- Point operator+(const Point& other) const {
- return Point(x + other.x, y + other.y);
- }
- Point operator*(const ld& other) const {
- return Point(x * other, y * other);
- }
- // векторное произведение sin
- ld operator^(const Point& other) const {
- return x * other.y - y * other.x;
- }
- // скалярное произведение cos
- ld operator*(const Point& other) const {
- return x * other.x + y * other.y;
- }
- ld len2() const {
- return sq(x) + sq(y);
- }
- ld len() const {
- return sqrt(len2());
- }
- Point norm() const {
- ld d = len();
- return Point(x / d, y / d);
- }
- bool operator<(const Point& other) const {
- if (sign(x - other.x) != 0) {
- return x < other.x;
- }
- else if (sign(y - other.y) != 0) {
- return y < other.y;
- }
- return false;
- }
- bool operator==(const Point& other) const {
- return sign(x - other.x) == 0 && sign(y - other.y) == 0;
- }
- Point ort() {
- return Point(-y, x);
- }
- void deb() const {
- std::cerr << "(" << x << ", " << y << ")" << std::endl;
- }
- };
- struct Line {
- ld a, b, c;
- Line() : a(0), b(0), c(0) {}
- 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) {
- ////// нормирование прямой
- //ld d = Point(a, b).len();
- //a /= d, b /= d, c /= d;
- //if (sign(a) == -1) {
- // a = -a;
- // b = -b;
- // c = -c;
- //}
- //else if (sign(a) == 0 && sign(b) == 0) {
- // a = 0;
- // b = -b;
- // c = -b;
- //}
- }
- bool operator==(const Line& other) const {
- return sign(a - other.a) == 0 && sign(b - other.b) == 0 && sign(c-other.c)==0;
- }
- };
- ld dist_points(Point a, Point b) {
- return sqrtl(sq(a.x - b.x) + sq(a.y - b.y));
- }
- bool is_point_on_seg(const Point& a, const Point& b, const Point& x) {
- return sign((a - b).len() - (a - x).len() - (b - x).len()) == 0;
- }
- ld dist_line(const Point& a, const Line& l) {
- return abs(l.a * a.x + l.b * a.y + l.c) / sqrt(sq(l.a) + sq(l.b));
- }
- ld get_dist_line(Point& a, Point& c, Point& d) {
- Line buf(c, d);
- return dist_line(a, buf);
- }
- ld dist_point_segment(Point& x, Point& c, Point& d) {
- Line check(c, d);
- ld dis = dist_line(x, check);
- Vec k(check.a, check.b);
- k = k.norm() * dis;
- Point suba = x + k;
- Point subb = x - k;
- if (is_point_on_seg(c, d, suba) || is_point_on_seg(c, d, subb)) {
- return dis;
- }
- else {
- return min(dist_points(x, c), dist_points(x, d));
- }
- }
- bool line_cross(const Line& a, const Line& b, Point& ans) {
- ld d = (a.b * b.a - a.a * b.b);
- if (sign(d) == 0)
- return false;
- ans.x = (b.b * a.c - b.c * a.b) / d;
- ans.y = (b.c * a.a - a.c * b.a) / d;
- return true;
- }
- bool segment_cross(const Point& a, const Point& b, const Point& c, const Point& d) {
- if (sign((a - b) ^ (c - d)) == 0) {
- return is_point_on_seg(a, b, c) ||
- is_point_on_seg(a, b, d) ||
- is_point_on_seg(c, d, a) ||
- is_point_on_seg(c, d, b);
- }
- Point ans;
- if (line_cross(Line(a, b), Line(c, d), ans)) {
- return is_point_on_seg(a, b, ans) && is_point_on_seg(c, d, ans);
- }
- }
- ld dist_seg_to_seg(Point a, Point b, Point c, Point d) {
- if (segment_cross(a, b, c, d)) {
- return 0;
- }
- 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)));
- }
- struct Polygon {
- vector<Point> p;
- };
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- srand(time(NULL));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cout << fixed << setprecision(10);
- ll n, a, b;
- cin >> n >> a >> b;
- vector<Polygon> mas(n);
- for (ll i = 0; i < n; i++) {
- Polygon& use = mas[i];
- ll k;
- cin >> k;
- use.p.resize(k);
- for (ll j = 0; j < k; j++) {
- cin >> use.p[j].x >> use.p[j].y;
- }
- }
- vector<vector<pair<ld,ll>>>gr(n);
- for (ll i = 0; i < n; i++) {
- Polygon& out = mas[i];
- for (ll j = 0; j < n; j++) {
- if (j == i)
- continue;
- auto ter = [&](Point& from, Polygon& b,pair<Point,ll> &ans) {
- ll l = 0, r = b.p.size() - 1;
- while (r - l > 2) {
- ll ml = l + (r - l) / 3, mr = r - (r - l) / 3;
- if (dist_points(from, b.p[ml]) > dist_points(from, b.p[mr])) {
- l = ml;
- }
- else {
- r = mr;
- }
- }
- ll mid = (r + l) / 2;
- ld d1 = dist_points(from, b.p[l]), d2 = dist_points(from, b.p[r]), d3 = dist_points(from, b.p[mid]);
- ld mn = min(d1, min(d2, d3));
- if (sign(d1 - mn) == 0) {
- ans = { b.p[l],l };
- }
- else if (sign(d2 - mn) == 0) {
- ans = { b.p[r],r };
- }
- else {
- ans = { b.p[mid],mid };
- }
- return mn;
- };
- Polygon& in = mas[j];
- ll l = 0, r = out.p.size() - 1;
- pair<Point,ll> ans2={in.p[0],0};
- while (r - l > 2) {
- ll ml = l + (r - l) / 3, mr = r - (r - l) / 3;
- if (ter(out.p[ml],in,ans2) > ter(out.p[mr],in,ans2)) {
- l = ml;
- }
- else {
- r = mr;
- }
- }
- pair<Point,ll> ans1;
- ll mid = (r + l) / 2;
- 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]);
- ld mn = min(d1, min(d2, d3));
- if (sign(d1 - mn) == 0) {
- ans1 = { out.p[l],l };
- }
- else if (sign(d2 - mn) == 0) {
- ans1 = { out.p[r],r };
- }
- else {
- ans1 = { out.p[mid],mid };
- }
- //out.p[ans1.second + 1 < out.p.size() ? ans1.second + 1 : 0]
- ll ind_seg1_1 = ans1.second - 1 >= 0 ? ans1.second - 1 : out.p.size() - 1;
- ll ind_seg1_2 = ans1.second + 1 < out.p.size() ? ans1.second + 1 : 0;
- ll ind_seg_2_1 = ans2.second - 1 >= 0 ? ans2.second - 1 : in.p.size() - 1;
- ll ind_seg_2_2 = ans2.second + 1 < in.p.size() ? ans2.second + 1 : 0;
- 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]));
- 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]));
- gr[i].push_back({ min(dist1,dist2),j});
- }
- }
- const ld inf = 1e18;
- vector<ld> dist(n, inf);
- a--, b--;
- dist[a] = 0;
- set < pair<ld, ll> > queue;
- queue.insert({ dist[a], a });
- while (!queue.empty()) {
- ll v = queue.begin()->second;
- queue.erase(queue.begin());
- for (ll j = 0; j < gr[v].size(); ++j) {
- ll u = gr[v][j].second;
- ld w = gr[v][j].first;
- if (dist[v] + w < dist[u]) {
- queue.erase({ dist[u], u });
- dist[u] = dist[v] + w;
- queue.insert({ dist[u], u });
- }
- }
- }
- cout << dist[b] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement