#include using namespace std; using ll = long long; using vi = vector; // Geometry struct pt { ll x, y; }; struct ln { pt p1, p2; }; ll sgn(ll v) { return (v == 0 ? 0 : (v > 0 ? 1 : -1)); } ll det(ll x1, ll y1, ll x2, ll y2) { return x1*y2-x2*y1; } ll det(ll x1, ll y1, ll x2, ll y2, ll cx, ll cy) { return det(x1-cx, y1-cy, x2-cx, y2-cy); } // Using determinants to calculate orientation, we calculate if the two lines // intersect. Specifically, we use that p1, p2, p3 clockwise // <=> det(p1, p2, p3) > 0. bool intersect(ln a, ln b) { if (max(a.p1.x, a.p2.x) < min(b.p1.x, b.p2.x)) return false; if (max(b.p1.x, b.p2.x) < min(a.p1.x, a.p2.x)) return false; if (max(a.p1.y, a.p2.y) < min(b.p1.y, b.p2.y)) return false; if (max(b.p1.y, b.p2.y) < min(a.p1.y, a.p2.y)) return false; ll d1 = sgn(det(a.p2.x, a.p2.y, b.p1.x, b.p1.y, a.p1.x, a.p1.y)); ll d2 = sgn(det(a.p2.x, a.p2.y, b.p2.x, b.p2.y, a.p1.x, a.p1.y)); ll d3 = sgn(det(b.p2.x, b.p2.y, a.p1.x, a.p1.y, b.p1.x, b.p1.y)); ll d4 = sgn(det(b.p2.x, b.p2.y, a.p2.x, a.p2.y, b.p1.x, b.p1.y)); return d1 * d2 <= 0 && d3 * d4 <= 0; } //-Geometry // UnionFind struct UnionFind { vi 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 get_size(int i) { return size[find(i)]; } 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]++; } }; //-UnionFind int main() { int n; cin >> n; // Start with an empty graph. ll V = 0, E = 0; vector lines; UnionFind uf(n); for (int i = 0; i < n; ++i) { ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // Add two vertices and an edge between them. V += 2; E += 1; lines.push_back(ln{pt{x1, y1}, pt{x2, y2}}); // If this edge intersects with another edge, split both edges // in half and add a vertex in the middle. for (int j = 0; j < i; ++j) { if (intersect(lines[i], lines[j])) { V += 1; E += 2; uf.merge(i, j); } } } // Euler's Formula (deriviation). ll C = uf.count(); // cerr << "C = " << C << ", V = " << V << ", E = " << E << endl; cout << (C + E - V) << endl; return 0; }