#include #include #include using namespace std; struct point { long double x, y; }; point operator+(point a, point b) { return {a.x + b.x, a.y + b.y}; } point operator-(point a, point b) { return {a.x - b.x, a.y - b.y}; } long double cross(point a, point b) { return a.x * b.y - b.x * a.y; } long double dot(point a, point b) { return a.x * b.x + b.y * a.y; } istream & operator>>(istream & in, point & p) { return in >> p.x >> p.y; } struct line { point a, b; }; istream & operator>>(istream & in, line & l) { return in >> l.a >> l.b; } bool lines_intersect(line l1, line l2){ auto d1 = l1.b - l1.a; auto d2 = l2.b - l2.a; auto c = l2.a - l1.a; auto den = cross(d1, d2); if(den == 0) { // parallel if(cross(c, d1) == 0) { // on the same line auto t0 = dot(c, d1) / dot(d1, d1); auto t1 = dot(l2.b - l1.a, d1) / dot(d1, d1); return (0 <= t0 && t0 <= 1) || (0 <= t1 && t1 <= 1); } else { return false; } } auto t = cross(c, d2) / den; auto s = cross(c, d1) / den; return 0 <= s && s <= 1 && 0 <= t && t <= 1; } int main (){ int N; cin >> N; std::vector lines(N); for(int i = 0; i < N; ++i) { cin >> lines[i]; } std::vector> graph(N); size_t points = 0; for(int i = 0; i < N; ++i) { for (int j = i+1; j < N; ++j) { if(lines_intersect(lines[i], lines[j])) { points++; graph[i].push_back(j); graph[j].push_back(i); } } } size_t edges = 0; for(int i = 0; i < N; ++i) { // lines wich do not intersect are skipped if(graph[i].size() > 0) { edges += graph[i].size() - 1; } } size_t components = 0; std::vector visited(N, false); queue work; for(int i = 0; i < N; ++i) { // lines wich do not intersect are skipped if(graph[i].empty()) continue; if(visited[i]) continue; work.push(i); components++; while(!work.empty()) { auto j = work.front(); work.pop(); if(visited[j]) continue; for(auto v : graph[j]) { if(visited[v]) continue; work.push(v); } visited[j] = true; } } // alternating sum: faces - edges + points - components = 0 size_t faces = edges - points + components; cout << faces << endl; }