#include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i)) using namespace std; struct strongly_connected_components { static pair > decompose(vector > const & g) { // adjacent list strongly_connected_components scc(g); return { scc.k, scc.c }; } private: int n; vector > to, from; explicit strongly_connected_components(vector > const & g) : n(g.size()), to(g), from(n) { repeat (i,n) for (int j : to[i]) from[j].push_back(i); decompose(); } vector used; vector vs; void dfs(int i) { used[i] = true; for (int j : to[i]) if (not used[j]) dfs(j); vs.push_back(i); } int k; // number of scc vector c; // i-th vertex in g is in c_i-th vertex in scc-decomposed g void rdfs(int i) { used[i] = true; c[i] = k; for (int j : from[i]) if (not used[j]) rdfs(j); } void decompose() { used.clear(); used.resize(n, false); repeat (i,n) if (not used[i]) dfs(i); used.clear(); used.resize(n, false); k = 0; c.resize(n); reverse(vs.begin(), vs.end()); for (int i : vs) if (not used[i]) { rdfs(i); k += 1; } } }; vector twosat(int n, vector > const & cnf) { // make digraph vector > g(2*n); auto i = [&](int x) { assert (x != 0 and abs(x) <= n); return x > 0 ? x-1 : n-x-1; }; for (auto it : cnf) { int x, y; tie(x, y) = it; // x or y g[i(- x)].push_back(i(y)); // not x implies y g[i(- y)].push_back(i(x)); // not y implies x } // do SCC vector component = strongly_connected_components::decompose(g).second; vector valuation(n); repeat_from (x,1,n+1) { if (component[i(x)] == component[i(- x)]) { // x iff not x return vector(); // unsat } valuation[x-1] = component[i(x)] > component[i(- x)]; // use components which indices are large } return valuation; } int main() { int n; scanf("%d", &n); vector y[2] = { vector(n), vector(n) }; vector x[2] = { vector(n), vector(n) }; repeat (i,n) scanf("%d%d%d%d", &y[0][i], &x[0][i], &y[1][i], &x[1][i]); vector > cnf; repeat (j,n) repeat (i,j) { repeat (p,2) repeat (q,2) { if (make_pair(y[p][i], x[p][i]) == make_pair(y[q][j], x[q][j])) { int vi = (i+1) * (p ? 1 : -1); int vj = (j+1) * (q ? 1 : -1); cnf.emplace_back(- vi, - vj); cnf.emplace_back(- vj, - vi); } } } bool is_sat = not twosat(n, cnf).empty(); printf("%s\n", is_sat ? "YES" : "NO"); return 0; }