#include #include #include #include #include using namespace std; template constexpr T Gcd(const T& a, const T& b) { return b != 0 ? Gcd(b, a%b) : a < 0 ? -a : a; } struct Fract { int64_t n = 0, d = 1; Fract(int64_t num, int64_t den) : n(num), d(den) { int64_t g = Gcd(n, d); n /= g; d /= g; if (d < 0) { n = -n; d = -d; } } bool operator==(const Fract& f) const { return n == f.n && d == f.d; } bool operator<(const Fract& f) const { return __int128(n)*__int128(f.d) < __int128(f.n)*__int128(d); } }; struct Point { int64_t x, y; Point operator-(const Point& p) const { return {x-p.x, y-p.y}; } }; // Positive if b points counterclockwise of a. int64_t CrossProd(const Point& a, const Point& b) { return a.x*b.y - a.y*b.x; } vector, int>>> linePoints; vector>> pointLines; vector lineUsed, pointUsed; int64_t ret; void doit(int ln, int lidx, int nv, bool first = false) { lineUsed[ln] = 1; for (int ldir = first ? 1 : -1; ldir <= 1; ldir += 2) { int olidx = lidx; for (lidx += ldir; lidx >= 0 && lidx < linePoints[ln].size(); lidx += ldir) { int pn = linePoints[ln][lidx].second; if (pointUsed[pn] == 2 && nv == linePoints.size()) ret++; if (pointUsed[pn]) break; pointUsed[pn] = 1; for (auto [ln2, lidx2] : pointLines[pn]) if (!lineUsed[ln2]) doit(ln2, lidx2, nv+1); } for (lidx -= ldir; lidx != olidx; lidx -= ldir) { int pn = linePoints[ln][lidx].second; pointUsed[pn] = 0; } } lineUsed[ln] = 0; } int main() { int N; while (cin >> N) { vector A(N), B(N); for (int i = 0; i < N; i++) cin >> A[i].x >> A[i].y >> B[i].x >> B[i].y; linePoints.resize(N); map, int> inters; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { int64_t cp1 = CrossProd(A[j]-A[i], B[i]-A[i]); int64_t cp2 = CrossProd(B[j]-A[i], B[i]-A[i]); if (cp1 == cp2) continue; pair inter{{A[j].x * (cp2-cp1) - (B[j].x-A[j].x) * cp1, cp2-cp1}, {A[j].y * (cp2-cp1) - (B[j].y-A[j].y) * cp1, cp2-cp1}}; int pn; if (inters.count(inter)) { pn = inters[inter]; } else { pn = inters.size(); inters[inter] = pn; } linePoints[i].emplace_back(inter, pn); linePoints[j].emplace_back(inter, pn); if (pointLines.size() <= pn) pointLines.resize(pn+1); pointLines[pn].emplace_back(i, 0); pointLines[pn].emplace_back(j, 0); } } for (auto& v : linePoints) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } for (int pn = 0; pn < pointLines.size(); pn++) { auto& v = pointLines[pn]; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (auto& [ln, lidx] : v) { for (lidx = 0; ; lidx++) { if (linePoints[ln][lidx].second == pn) break; } } } lineUsed = vector(linePoints.size()); pointUsed = vector(pointLines.size()); ret = 0; for (int i = 0; i < linePoints[0].size(); i++) { int pn = linePoints[0][i].second; pointUsed[pn] = 2; doit(0, i, 1, true); pointUsed[pn] = 0; } cout << ret << endl; } }