#include #include #include using namespace std; struct point { 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}; } double cross(point a, point b) { return a.x * b.y - b.x * a.y; } 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){ point d1 = l1.b - l1.a; point d2 = l2.b - l2.a; point c = l2.a - l1.a; double den = cross(d1, d2); if(den == 0) { // parallel if(cross(c, d1) == 0) { // on the same line double t0 = dot(c, d1) / dot(d1, d1); double t1 = dot(l2.b - l1.a, d1) / dot(d1, d1); return (0 <= t0 && t0 <= 1) || (0 <= t1 && t1 <= 1); } else { return false; } } double t = cross(c, d2) / den; double 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 size_t faces = edges - points + components; cout << faces << endl; }