#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define fore(i, l, r) for(int i = (l); i < (r); ++i) #define forn(i, n) fore(i, 0, n) #define fori(i, l, r) fore(i, l, (r) + 1) #define sz(v) int((v).size()) #define all(v) (v).begin(), (v).end() #define pb push_back #define mp make_pair #define X first #define Y second #if ( _WIN32 || __WIN32__ ) #define LLD "%I64d" #else #define LLD "%lld" #endif typedef long long li; typedef long double ld; typedef pair pt; template T abs(T a) { return a < 0 ? -a : a; } template T sqr(T a) { return a*a; } const int INF = (int)1e9; const ld EPS = 1e-9; const ld PI = 3.1415926535897932384626433832795; /* This is just to check correctness of input */ void ensure(bool value){ if(!value){ fprintf(stderr, "Assertion failed"); throw; } } void ensure(bool value, string message){ if(!value){ fprintf(stderr, "Assertion failed. Message = %s", message.c_str()); throw; } } int readInt(int l, int r){ int x; if(scanf("%d", &x) != 1){ fprintf(stderr, "Expected int in range [%d, %d], but haven't found!", l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected int in range [%d, %d], but found %d!", l, r, x); throw; } return x; } int readInt(int l, int r, string name){ int x; if(scanf("%d", &x) != 1){ fprintf(stderr, "Expected int %s in range [%d, %d], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected int %s in range [%d, %d], but found %d!", name.c_str(), l, r, x); throw; } return x; } li readLong(li l, li r){ li x; if(scanf(LLD, &x) != 1){ fprintf(stderr, "Expected long long in range ["LLD", "LLD"], but haven't found!", l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected long long in range ["LLD", "LLD"], but found "LLD"!", l, r, x); throw; } return x; } li readLong(li l, li r, string name){ li x; if(scanf(LLD, &x) != 1){ fprintf(stderr, "Expected long long %s in range ["LLD", "LLD"], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected long long %s in range ["LLD", "LLD"], but found "LLD"!", name.c_str(), l, r, x); throw; } return x; } const ld __EPS__ = 1e-15; ld readDouble(double l, double r){ double x; if(scanf("%lf", &x) != 1){ fprintf(stderr, "Expected double in range [%lf, %lf], but haven't found!", l, r); throw; } if(!(l <= x + __EPS__ && x <= r + __EPS__)){ fprintf(stderr, "Expected double in range [%lf, %lf], but found %lf!", l, r, x); throw; } return x; } ld readDouble(double l, double r, string name){ double x; if(scanf("%lf", &x) != 1){ fprintf(stderr, "Expected double %s in range [%lf, %lf], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x + __EPS__ && x <= r + __EPS__)){ fprintf(stderr, "Expected double %s in range [%lf, %lf], but found %lf!", name.c_str(), l, r, x); throw; } return x; } const int __MAXBUF__ = (int)1e7; char __buf__[__MAXBUF__]; string readString(char lfc, char rgc, int lfn, int rgn){ ensure(scanf(" %s ", __buf__) == 1, "Expected string, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String have incorrect length"); forn(i, sz(ans)) ensure(lfc <= ans[i] && ans[i] <= rgc, "String contains incorrect characters"); return ans; } string readString(string pat, int lfn, int rgn){ ensure(scanf(" %s ", __buf__) == 1, "Expected string, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String have incorrect length"); forn(i, sz(ans)) ensure(find(all(pat), ans[i]) != pat.end(), "String contains incorrect characters"); return ans; } string readString(char lfc, char rgc, int lfn, int rgn, string name){ ensure(scanf(" %s ", __buf__) == 1, "Expected string " + name + ", haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String " + name + " have incorrect length"); forn(i, sz(ans)) ensure(lfc <= ans[i] && ans[i] <= rgc, "String " + name + " contains incorrect characters"); return ans; } string readString(string pat, int lfn, int rgn, string name){ ensure(scanf(" %s ", __buf__) == 1, "Expected string " + name + ", haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "String " + name + " have incorrect length"); forn(i, sz(ans)) ensure(find(all(pat), ans[i]) != pat.end(), "String " + name + " contains incorrect characters"); return ans; } string readLine(char lfc, char rgc, int lfn, int rgn){ ensure(gets(__buf__) != NULL, "Line expected, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "Line have incorrect length"); forn(i, sz(ans)) ensure(lfc <= ans[i] && ans[i] <= rgc, "Line contains incorrect characters"); return ans; } string readLine(string pat, int lfn, int rgn){ ensure(gets(__buf__) != NULL, "Line expected, haven't found"); string ans = __buf__; ensure(lfn <= sz(ans) && sz(ans) <= rgn, "Line have incorrect length"); forn(i, sz(ans)) ensure(find(all(pat), ans[i]) != pat.end(), "Line contains incorrect characters"); return ans; } string readLine(){ ensure(gets(__buf__) != NULL, "Line expected, haven't found"); string ans = __buf__; return ans; } char readChar(){ char c; ensure(scanf(" %c ", &c) == 1, "Non-whitespace character expected"); return c; } char readWChar(){ int ans = getchar(); ensure(ans != EOF, "Character expected"); return (char)ans; } const int NMAX = 110; int n; pt p[NMAX]; string g[NMAX]; pt operator - (const pt& a, const pt& b){ return pt(a.X - b.X, a.Y - b.Y); } li vmul(const pt& a, const pt& b){ return a.X * 1LL * b.Y - a.Y * 1LL * b.X; } int pr[NMAX], dep[NMAX], used[NMAX]; vector ord; inline int area (pt a, pt b, pt c) { return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X); } inline bool intersect_1 (int a, int b, int c, int d) { if (a > b) swap (a, b); if (c > d) swap (c, d); return max(a,c) <= min(b,d); } bool intersect (pt a, pt b, pt c, pt d) { return intersect_1 (a.X, b.X, c.X, d.X) && intersect_1 (a.Y, b.Y, c.Y, d.Y) && area(a,b,c) * area(a,b,d) <= 0 && area(c,d,a) * area(c,d,b) <= 0; } vector order; void dfs(int v, int par, int curdep){ pr[v] = par; dep[v] = curdep; used[v] = true; ord.pb(p[v]); random_shuffle(all(order)); forn(ui, sz(order)){ int u = order[ui]; if(g[v][u] == 'Y' && !used[u]){ bool ok = true; fori(k, 0, sz(ord) - 3){ if(intersect(ord[k], ord[k + 1], ord.back(), p[u])){ ok = false; break; } } if(ok){ dfs(u, v, curdep + 1); } } } ord.pop_back(); } vector go(int v){ memset(pr, -1, sizeof pr); memset(dep, 0, sizeof dep); memset(used, 0, sizeof used); dfs(v, -1, 0); int start = max_element(dep, dep + n) - dep; vector res; for(int cur = start; cur != -1; cur = pr[cur]){ res.pb(cur); } return res; } int main(){ #ifdef ssu1 freopen("input.txt", "rt", stdin); //freopen("output.txt", "wt", stdout); #endif n = readInt(20, 50, "n"); forn(i, n) order.pb(i); forn(i, n){ p[i].X = readInt(0, 100, "x"); p[i].Y = readInt(0, 100, "y"); } readLine(); vector conn(n); forn(i, n){ g[i] = readLine(); ensure(sz(g[i]) == n); forn(j, n){ ensure(g[i][j] == 'Y' || g[i][j] == 'N'); if(g[i][j] == 'Y'){ conn[i]++; conn[j]++; } } } forn(i, n){ ensure(conn[i] > 0, "conn[i] > 0"); } forn(i, n){ forn(j, i){ forn(k, j){ ensure(vmul(p[j] - p[i], p[k] - p[i]) != 0); } } } vector > ans; while(true){ vector ok; forn(v, n){ forn(ITER, 2){ vector cur = go(v); if(sz(cur) > sz(ok)) ok = cur; } } if(sz(ok) == 1) break; forn(i, sz(ok)) forn(j, i) ensure(ok[i] != ok[j]); ans.pb(ok); forn(i, sz(ok) - 1){ g[ok[i]][ok[i + 1]] = g[ok[i + 1]][ok[i]] = 'N'; } } printf("%d\n", sz(ans)); forn(i, sz(ans)){ printf("%d", sz(ans[i]) - 1); forn(j, sz(ans[i])){ printf(" %d", ans[i][j]); } puts(""); } return 0; }