#include #include #include #include #include #include #include #include #include #include using namespace std; void commit(int ans) { cout << ans << "\n"; exit(0); } array getxpt(int64_t sx, int64_t sy, int64_t tx, int64_t ty) { array val = { tx*(ty-sy) - ty*(tx-sx), ty-sy }; int64_t g = gcd(val[0], val[1]); val[0] /= g; val[1] /= g; if(val[1] < 0) { val[1] *= -1; val[0] *= -1; } return val; } int sgn(int x) { return (x>0)-(x<0); } int main() { int n, unusedvalue; cin >> n >> unusedvalue; vector> segs(n); for(auto& x: segs) cin >> x[0] >> x[1] >> x[2]; sort(segs.begin(), segs.end()); // if all the segments overlap, infinite { map dp; for(int i = 0; i < n; i++) { dp[segs[i][1]]++; dp[segs[i][2]]--; } int biggest = dp.rbegin()->first; int lhs = 1; int curr = 0; for(auto [k, v]: dp) { if(k == biggest) break; curr += v; lhs = min(lhs, curr); } if(lhs > 0) commit(-1); } vector ord(2*n); vector loc(2*n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int a, int b) -> bool { return segs[a/2][1+a%2] < segs[b/2][1+b%2]; }); vector dp(2*n+1); vector coverage(n+1); for(int i = 0; i < 2*n; i++) { dp[i+1] = dp[i] + (1 - (ord[i]%2)*2); if(i != 2*n-1) coverage[dp[i+1]]++; loc[ord[i]] = i; } vector, array>> events; for(int i = 0; i < n; i++) for(int j = i+1; j < n; j++) { for(int a = 1; a < 3; a++) for(int b = 1; b < 3; b++) { if(sgn(segs[i][a]) != sgn(segs[j][b])) continue; array x = getxpt(segs[i][0], segs[i][a], segs[j][0], segs[j][b]); if(x[0] >= 0) continue; if(segs[i][a] < segs[j][b]) events.emplace_back(x, array({(2*i)|(a-1), (2*j)|(b-1)})); else events.emplace_back(x, array({(2*j)|(b-1), (2*i)|(a-1)})); } } double ret = 0; sort(events.begin(), events.end(), [&](auto& a, auto& b) -> bool { if(a.first != b.first) { return a.first[0] * b.first[1] < a.first[1] * b.first[0]; } int ai = a.second[0], aj = a.second[1], bi = b.second[0], bj = b.second[1]; if(segs[ai/2][1+ai%2] != segs[bi/2][1+bi%2]) return segs[ai/2][1+ai%2] < segs[bi/2][1+bi%2]; return segs[aj/2][1+aj%2] < segs[bj/2][1+bj%2]; }); double lhs = -1e100; for(int i = 0; i < events.size();) { int j = i; if(coverage[0] == 0) ret += events[i].first[0] / double(events[i].first[1]) - lhs; while(j < events.size() && events[i].first == events[j].first) { // process event j auto [li, ri] = events[j++].second; assert(loc[li] + 1 == loc[ri]); int lmask = (li&1); int rmask = (ri&1); if(lmask==0 && rmask==1) { coverage[dp[loc[li]+1]]--; dp[loc[li]+1] -= 2; coverage[dp[loc[li]+1]]++; } else if(lmask==1 && rmask==0) { coverage[dp[loc[li]+1]]--; dp[loc[li]+1] += 2; coverage[dp[loc[li]+1]]++; } swap(loc[li], loc[ri]); ord[loc[li]] = li; ord[loc[ri]] = ri; } lhs = events[i].first[0] / double(events[i].first[1]); i = j; } if(coverage[0] == 0) ret -= lhs; cout << fixed << setprecision(39) << ret << "\n"; }