#include using namespace std; //#define int long long #define rep(i, a, b) for (int i = a; i < (b); ++i) #define f(i,a,b) for(int i = (a); i < (b); ++i) using ld = long double; using ll = long long; #define double long double typedef vector vi; template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x = 0, T y = 0) : x(x), y(y) {} bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); } bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); } P operator+(P p) const { return P(x + p.x, y + p.y); } P operator-(P p) const { return P(x - p.x, y - p.y); } P operator*(T d) const { return P(x * d, y * d); } P operator/(T d) const { return P(x / d, y / d); } T dot(P p) const {return x * p.x + y * p.y;} T cross(P p) const {return x*p.y - y * p.x; } T cross(P a, P b) const {return (a - *this).cross(b - *this);} T dist2() const {return x * x + y * y;} double dist() const {return sqrt((double)dist2());} double angle() const {return atan2(y, x);} P unit() const {return *this/dist();} P perp() const {return P(-y, x);} P normal() const {return perp().unit();} P rotate(double a) { return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << ", " << p.y << ")"; } }; template bool onSegment(P s, P e, P p) { return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0; } template bool segInter(P a, P b, P c, P d) { auto oa = c.cross(d, a), ob = c.cross(d, b), oc = a.cross(b, c), od = a.cross(b, d); if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) return true; return false; } typedef Point P; vector

convexHull(vector

pts) { if (pts.size() <= 1) return pts; sort(pts.begin(), pts.end()); vector

h(pts.size() + 1); int s = 0, t = 0; for (int it = 2; it--; s = --t, reverse(pts.begin(), pts.end())) { for (P p : pts) { while (t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--; h[t++] = p; } } return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])}; } #define ld long double struct Node { vector nbs; vector dist; bool set = false; }; signed main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector vals; int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty; vector

points; vector> hulls(n); points.push_back(P{sx, sy}); points.push_back(P{tx, ty}); vector ptoh{-1, -2}; for (int i = 0; i < n; ++i) { int c; cin >> c; hulls[i].resize(c); for (int j = 0; j < c; ++j) ptoh.push_back(i); for (auto &p : hulls[i]) { cin >> p.x >> p.y; points.push_back(P{p.x, p.y}); } } vals = vector (points.size()); for (int i = 0; i < points.size(); ++i) { for (int j = i + 1; j < points.size(); ++j) { if (ptoh[i] == ptoh[j]) { int ind = -1; for (int k = 0; k < hulls[ptoh[i]].size(); ++k) { if (hulls[ptoh[i]][k] == points[i]) { ind = k; break; } } if (ind == -1) continue; int ind2 = (ind + 1) % hulls[ptoh[i]].size(); if (!(hulls[ptoh[i]][ind2] == points[j])) { ind2 = (ind - 1 + (int)hulls[ptoh[i]].size()) % hulls[ptoh[i]].size(); if (!(hulls[ptoh[i]][ind2] == points[j])) continue; } } bool res = true; for (auto &hull: hulls) { if (segInter(points[i], points[j], hull.front(), hull.back())) { res = false; break; } for (int k = 0; k + 1 < hull.size(); ++k) { if (segInter(points[i], points[j], hull[k], hull[k + 1])) { res = false; break; } } if (!res) break; } if (res) { ld dist = (points[i] - points[j]).dist(); vals[i].nbs.push_back(j); vals[i].dist.push_back(dist); vals[j].nbs.push_back(i); vals[j].dist.push_back(dist); } } } priority_queue> q; q.push({0,0}); while(!q.empty()) { auto top = q.top(); q.pop(); ld dist = -top.first; int who = top.second; if (who == 1) { cout << setprecision(17) << fixed << dist << "\n"; return 0; } if (vals[who].set) continue; vals[who].set = true; //cerr << who << " " << dist << endl; f(i,0,vals[who].nbs.size()) { q.push({-dist - vals[who].dist[i], vals[who].nbs[i]}); } } return 0; } /* * 2 0 0 5 1 4 1 1 2 1 1 -4 2 -4 4 3 0 4 0 3 3 4 3 1 0 0 4 0 5 1 3 2 4 3 3 1 -10 3 -10 */