// // Faulty solution to problem Fences // By Mees de Vries // // Expected judgment: WRONG ANSWER // // Doesn't deal with multiple connected components of lines. #include #include #include using namespace std; #define ll long long struct pt { ll x; ll y; }; bool operator==(const pt& l, const pt& r) { return l.x == r.x && l.y == r.y; } // orientation (positive, negative, collinear). ll ort(pt a, pt b, pt c) { return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y); } // does c lie on a - b. bool pointonline(pt a, pt b, pt c) { return ort(a,b,c) == 0 && b.x <= max(a.x,c.x) && b.x >= min(a.x,c.x) && b.y <= max(a.y,c.y) && b.y >= min(a.y,c.y); } // do a-b and c-d intersect bool segint(pt a, pt b, pt c, pt d) { if((ort(a,b,c)*ort(a,b,d) <= 0 && !(ort(a,b,c)==0 && ort(a,b,d)==0)) && (ort(c,d,a)*ort(c,d,b) <= 0 && !(ort(c,d,a)==0 && ort(c,d,b)==0))) { return true; } if(pointonline(a,c,b) || pointonline(a,d,b) || pointonline(c,a,d) || pointonline(c,b,d)) return true; return false; } int main() { int n; cin >> n; vector A(n), B(n); vector intersections(n,0); for(int i = 0; i < n; i++) { cin >> A[i].x >> A[i].y >> B[i].x >> B[i].y; } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if(segint(A[i],B[i],A[j],B[j])) { intersections[i]++; intersections[j]++; } } } // Count vertices and edges in the graph given by the lines. int verts = 0, edges = 0; for(int i = 0; i < n; i++) { verts += intersections[i]; edges += intersections[i] - 1; } verts /= 2; cout << 1 - verts + edges << endl; return 0; }