#include #include #include #include #include #include #include using namespace std; template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P perp() const { return P(-y, x); } // rotates +90 degrees // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } }; typedef Point p; template int lineIntersection(const P& s1, const P& e1, const P& s2, const P& e2, P& r) { if ((e1-s1).cross(e2-s2)) { //if not parallell r = s2-(e2-s2)*(e1-s1).cross(s2-s1)/(e1-s1).cross(e2-s2); return 1; } else return -((e1-s1).cross(s2-s1)==0 || s2==e2); } const double EPS = 1e-25; const int N = 12; p src[N]; p dst[N]; vector

allintersections; int n; vector> edges[N*(N-1)/2]; bool bad[N*(N-1)/2]; int dfs(int curr, int currcolor, int emask, const int dst) { if(curr == dst) { if(emask == (1 << n) - 1) return 1; if(emask) return 0; } int ret = 0; bad[curr] = true; for(auto out: edges[curr]) { if(bad[out.first]) continue; if(out.second != currcolor && emask & (1 << out.second)) continue; ret += dfs(out.first, out.second, emask | (1 << out.second), dst); } bad[curr] = false; return ret; } int main() { cin >> n; for(int i = 0; i < n; i++) { cin >> src[i].x >> src[i].y >> dst[i].x >> dst[i].y; for(int j = 0; j < i; j++) { p cand; if(lineIntersection(src[i], dst[i], src[j], dst[j], cand)) { bool found = false; for(auto out: allintersections) if((out-cand).dist2() <= EPS) found = true; if(!found) allintersections.push_back(cand); } } } for(int i = 0; i < n; i++) { vector> locs; for(int j = 0; j < n; j++) { if(i == j) continue; p cand; if(lineIntersection(src[i], dst[i], src[j], dst[j], cand)) { int idx = -1; for(int a = 0; a < (int)allintersections.size(); a++) { long double dd = (cand - allintersections[a]).dist2(); if(dd <= EPS) { assert(idx < 0); idx = a; } } if(idx >= 0) { locs.emplace_back(cand, idx); } } } sort(locs.begin(), locs.end()); for(int a = 1; a < (int)locs.size(); a++) { edges[locs[a-1].second].emplace_back(locs[a].second, i); edges[locs[a].second].emplace_back(locs[a-1].second, i); } } int ret = 0; for(int i = 0; i < (int)allintersections.size(); i++) { for(auto out: edges[i]) { if(out.second) continue; ret += dfs(out.first, out.second, 1 << out.second, i); } } cout << ret/2 << "\n"; }