#include #include #include #include using namespace std ; using ll = long long ; using pt = pair ; using rat = double ; using rpt = pair ; using line = pair ; const int MAX = 32 ; rpt inter[MAX][MAX] ; rat pos(ll num, ll den) { return num / (double)den ; } rpt lineline(line a, line b) { auto [p1, p2] = a ; auto [p3, p4] = b ; auto [x1, y1] = p1 ; auto [x2, y2] = p2 ; auto [x3, y3] = p3 ; auto [x4, y4] = p4 ; auto d = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4) ; if (d == 0) return {INFINITY,INFINITY} ; return {pos((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4),d), pos((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4),d)} ; } int eq(rat &a, rat &b) { return a == b ; } int eq(rpt &a, rpt &b) { return eq(a.first, b.first) && eq(a.second, b.second) ; } int cmp(rat &a, rat &b) { rat t = a - b ; if (t < 0) return -1 ; if (t > 0) return 1 ; return 0 ; } int inbounds(rpt &p, rpt &a, rpt &b) { return (cmp(p.first, a.first) * cmp(b.first, p.first) >= 0) && (cmp(p.second, a.second) * cmp(b.second, p.second) >= 0) ; } int segseg(int a, int b, int c, int d, int e, int f) { auto &cross = inter[b][e] ; if (cross.first == INFINITY) return 0 ; return inbounds(cross, inter[a][b], inter[b][c]) && inbounds(cross, inter[d][e], inter[e][f]) ; } vector poly ; vector v ; int n ; ll r = 0 ; void recur(int lastlin, ll used, int togo) { int ps = poly.size() ; if (togo == 0) { if (eq(inter[poly[0]][poly[1]], inter[poly[ps-2]][poly[ps-1]])) return ; poly.push_back(poly[1]) ; for (int j=1; j+2<=ps-2; j++) { if (segseg(poly[j], poly[j+1], poly[j+2], poly[ps-2], poly[ps-1], poly[ps])) { poly.pop_back() ; return ; } } poly.pop_back() ; r++ ; return ; } for (int i=0; i> i) & 1) == 0) { if (ps > 1 && eq(inter[i][poly[ps-1]], inter[poly[ps-1]][poly[ps-2]])) continue ; if (inter[i][poly[ps-1]].first != INFINITY) { int good = 1 ; for (int j=0; good && j+2<=ps-2; j++) { if (segseg(poly[j], poly[j+1], poly[j+2], poly[ps-2], poly[ps-1], i)) good = 0 ; } if (good) { poly.push_back(i) ; recur(i, used | (1LL << i), togo-1) ; poly.pop_back() ; } } } } int main() { cin >> n ; v.resize(n) ; for (auto &[p1, p2] : v) { auto& [x1, y1] = p1 ; auto& [x2, y2] = p2 ; cin >> x1 >> y1 >> x2 >> y2 ; } for (int i=0; i>1) << endl ; }