// imprement 50min // debug 15min #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const long double EPS = 1e-9; static const long double INF = 1e+8; static const long double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) #include typedef complex Point; typedef vector Polygon; #define CURR(P, i) (P[(i + 0) % P.size()]) #define NEXT(P, i) (P[(i + 1) % P.size()]) struct Line : public vector { Line() {;} Line(Point a, Point b) { push_back(a); push_back(b); } }; struct Circle { Point p; long double r; Circle() {;} Circle(Point p, long double r) : p(p), r(r) {;} }; namespace std { bool operator<(const Point &lhs, const Point &rhs) { return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real(); } } inline long double cross(const Point &a, const Point &b) { return imag(conj(a) * b); } inline long double dot(const Point &a, const Point &b) { return real(conj(a) * b); } inline int ccw(Point a, Point b, Point c) { b -= a; c -= a; if (cross(b, c) > 0) { return 1; } if (cross(b, c) < 0) { return -1; } if (dot(b, c) < 0) { return 2; } if (norm(b) < norm(c)) { return -2; } return 0; } bool intersectLL(const Line &l, const Line &m) { return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || abs(cross(l[1] - l[0], m[0] - l[0])) < EPS; } bool intersectSP(const Line &s, const Point &p) { return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; } Point projection(const Line &l, const Point &p) { long double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]); return l[0] + t * (l[0] - l[1]); } long double distanceSP(const Line &s, const Point &p) { const Point r = projection(s, p); if (intersectSP(s, r)) { return abs(r - p); } return min(abs(s[0] - p), abs(s[1] - p)); } bool intersectSC(const Line &s, const Circle &c) { return distanceSP(s, c.p) <= c.r; } //======================================== struct Input { int n; Point start; Point end; vector rs; vector route; Input() {;} }; namespace Solver { struct Event { long double t; int index; Event() {;} Event(long double t, int index) : t(t), index(index) {;} bool operator<(const Event &rhs) const { return t > rhs.t; } }; int n; vector rs; vector route; long double ls[110]; bool matrix[110][110]; void calc_event(int index, priority_queue &que) { long double t = 0; REP(i, route[index].size()) { t += abs(NEXT(route[index], i) - CURR(route[index], i)) / ls[index]; que.push(Event(t, index)); } } Point calc_vect(int from, int i, int to, int j) { Point v1 = (NEXT(route[from], i) - CURR(route[from], i)); Point v2 = (NEXT(route[to], j) - CURR(route[to], j)); v1 *= ls[from] / abs(v1); v2 *= ls[to] / abs(v2); if (isnan(v1.real())) { v1 = Point(0, 0); } if (isnan(v2.real())) { v2 = Point(0, 0); } return v2 - v1; } bool calc(int from, int to) { priority_queue que; calc_event(from, que); calc_event(to, que); long double t = 0; int i1 = 0; int i2 = 0; Circle c(Point(0, 0), rs[from] + rs[to]); Point pos = route[to][0] - route[from][0]; while (!que.empty()) { Event event = que.top(); que.pop(); long double d = event.t - t; Point vect = calc_vect(from, i1, to, i2); Point npos = pos + vect * d; if (intersectSC(Line(pos, npos), c)) { return true; } t = event.t; pos = npos; if (event.index == from) { i1++; } else { i2++; } } assert(abs(pos - (route[to][0] - route[from][0])) < EPS); return false; } bool solv(const Input &input) { // init MEMSET(ls, 0xff); MEMSET(matrix, 0); n = input.n + 2; rs = input.rs; rs.push_back(0); rs.push_back(0); route = input.route; route.push_back(Polygon(1, input.end)); route.push_back(Polygon(1, input.start)); // // initial condition check // REP(i, n - 1) { // if (input.rs[i] > abs(input.start - input.route[i][0])) { matrix[n][i] = true; } // } // calc REP(i, n) { long double l = 0; REP(j, route[i].size()) { l += abs(NEXT(route[i], j) - CURR(route[i], j)); } if (l == 0) { l = 1e+10; } ls[i] = l; } REP(i, n) { matrix[i][i] = true; REP(j, n) { if (i == j) { continue; } matrix[i][j] = calc(i, j); } } // REP(y, n) { // REP(x, n) { // cout << (matrix[y][x] ? "1" : "."); // } // cout << endl; // } // end REP(k, n) REP(i, n) REP(j, n) { matrix[i][j] |= matrix[i][k] && matrix[k][j]; } return matrix[n - 1][n - 2]; } }; int main() { int n; while (scanf("%d", &n) > 0) { Input input; input.n = n; long double sx, sy, ex, ey; int v = scanf("%Lf %Lf %Lf %Lf", &sx, &sy, &ex, &ey); assert(v == 4); input.start = Point(sx, sy); input.end = Point(ex, ey); input.rs = vector(n, 0); input.route = vector(n); REP(i, n) { long double r; int k; int v = scanf("%Lf %d", &r, &k); assert(v == 2); input.rs[i] = r; REP(j, k) { long double x, y; int v = scanf("%Lf %Lf", &x, &y); assert(v == 2); input.route[i].push_back(Point(x, y)); } } bool ans = Solver::solv(input); printf(ans ? "Yes\n" : "No\n"); } }