#include #include #include using namespace std; struct UnionFind { vector par, rank, size; int c; UnionFind(int n) : par(n), rank(n, 0), size(n, 1), c(n) { for(int i = 0; i < n; ++i) par[i] = i; } int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); } bool same(int i, int j) { return find(i) == find(j); } int count() { return c; } void merge(int i, int j) { if((i = find(i)) == (j = find(j))) return; c--; if(rank[i] > rank[j]) swap(i, j); par[i] = j; size[j] += size[i]; if(rank[i] == rank[j]) rank[j]++; } }; using P = array; using S = array; P operator-(const P &l, const P &r) { return {{l[0] - r[0], l[1] - r[1]}}; } int sign(long long x) { return (x > 0) - (x < 0); } int det(const P &l, const P &r) { return sign(l[0] * r[1] - l[1] * r[0]); } int det(const P &p, const P &q, const P &r) { return det(p - r, q - r); } bool intersect(const S &l, const S &r) { // edge case for 2 line segments on the same line for(int i : {0, 1}) if(max(l[0][i], l[1][i]) < min(r[0][i], r[1][i]) || min(l[0][i], l[1][i]) > max(r[0][i], r[1][i])) return false; return det(l[0], l[1], r[0]) * det(l[0], l[1], r[1]) <= 0 && det(r[0], r[1], l[0]) * det(r[0], r[1], l[1]) <= 0; } int main() { int n; cin >> n; vector ss(n); for(auto &s : ss) cin >> s[0][0] >> s[0][1] >> s[1][0] >> s[1][1]; // P-E+F-C=1 => F = 1+E-P+C -1 (-1, because infinite region is excluded) int E = n, P = 2 * n; UnionFind uf(n); for(int i = 0; i < n; ++i) for(int j = 0; j < i; ++j) if(intersect(ss[i], ss[j])) uf.merge(i, j), E += 2, P += 1; cerr << "E: " << E << endl; cerr << "P: " << P << endl; cerr << "C: " << uf.count() << endl; cout << E - P + uf.count() << endl; return 0; }