/* -*- coding: utf-8 -*- * * 483.cc: No.483 マッチ並べ - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100; const int MAX_GN = MAX_N * 2; const int MAX_X = 100; const int MAX_Y = 100; /* typedef */ typedef vector vi; typedef queue qi; typedef pair pii; /* global variables */ int gn = 0, gids[MAX_Y][MAX_X]; vi nbrs[MAX_GN]; bool used[MAX_GN], lps[MAX_GN], used1[MAX_GN]; int prvs[MAX_GN]; /* subroutines */ inline int readgid(int y, int x) { return (gids[y][x] < 0) ? (gids[y][x] = gn++) : gids[y][x]; } void finish_no() { puts("NO"); exit(0); } /* main */ int main() { memset(gids, -1, sizeof(gids)); int n; cin >> n; for (int i = 0; i < n; i++) { int y0, x0, y1, x1; cin >> y0 >> x0 >> y1 >> x1; y0--, x0--, y1--, x1--; int u = readgid(y0, x0); int v = readgid(y1, x1); nbrs[u].push_back(v); nbrs[v].push_back(u); } //printf("gn=%d\n", gn); for (int st = 0; st < gn; st++) { if (used[st]) continue; qi q; q.push(st); used[st] = true; prvs[st] = -1; vi lv; bool ok = true; while (ok && ! q.empty()) { int u = q.front(); q.pop(); vi &nbru = nbrs[u]; for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &v = *vit; if (v == prvs[u]) continue; if (! used[v]) { q.push(v); used[v] = true; prvs[v] = u; } else { for (int i = v; i >= 0; i = prvs[i]) lv.push_back(i), lps[i] = true; vi lv1; for (int i = u; i >= 0 && ! lps[i]; i = prvs[i]) lv1.push_back(i), lps[i] = true; for (int i = lv1.size() - 1; i >= 0; i--) lv.push_back(lv1[i]); ok = false; break; } } } if (ok) continue; int lvn = lv.size(); //printf("lv=%d\n", lvn); //for (int i = 0; i < gn; i++) printf("%d ", lps[i]); putchar('\n'); qi q1; for (int i = 0; i < lvn; i++) { int &u = lv[i], &u0 = lv[(i + lvn - 1) % lvn], &u1 = lv[(i + 1) % lvn]; used1[u] = used[u] = true; prvs[u] = -1; vi &nbru = nbrs[u]; for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &v = *vit; if (v != u0 && v != u1) { if (lps[v] || used1[v]) finish_no(); q1.push(v); used1[v] = used[v] = true; prvs[v] = u; } } } while (! q1.empty()) { int u = q.front(); q.pop(); vi &nbru = nbrs[u]; for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &v = *vit; if (v == prvs[u]) continue; if (! lps[v] && ! used1[v]) { q1.push(v); used1[v] = used[v] = true; prvs[v] = u; } else finish_no(); } } } puts("YES"); return 0; }