// @@bs25-8@@ #include #include #include #include #include #include #include #include #include #include #include template std::vector compress(const std::vector& data) { std::vector compressed(data); std::sort(compressed.begin(), compressed.end()); compressed.erase(std::unique(compressed.begin(), compressed.end()), compressed.end()); return compressed; } template int64_t lookup(const std::vector& data, T val) { auto it = std::lower_bound(data.begin(), data.end(), val); return std::distance(data.begin(), it); } // 0 indexed template template > struct BIT { static constexpr T UNIT = 0; int32_t n; F f; std::vector f_tree; BIT(int32_t n): n(n), f() { f_tree.assign(n + 1, UNIT); } // data[x] = f(data[x], v) void update(int32_t x, T v) { for (++x; x <= n; x += (x & -x)) { f_tree[x] = f(f_tree[x], v); } } // f applied to range [0..x) T query(int32_t x) const { T res = UNIT; for (; x > 0; x -= (x & -x)) { res = f(res, f_tree[x]); } return res; } }; template > struct BIT2 { int32_t n; F f; std::vector> f_tree; std::vector> vals; BIT2(int32_t n): n(n), f() { f_tree.reserve(n + 1); vals.resize(n + 1); } void insert(int32_t idx, int64_t v) { assert(0 <= idx && idx < n); for (++idx; idx <= n; idx += (idx & -idx)) { vals[idx].push_back(v); } } void finalize() { f_tree.emplace_back(0); for (int32_t i = 1; i <= n; ++i) { vals[i] = compress(vals[i]); f_tree.emplace_back(vals[i].size()); } } void update(int32_t idx, int64_t v, T d) { assert(0 <= idx && idx < n); for (++idx; idx <= n; idx += (idx & -idx)) { auto idx2 = lookup(vals[idx], v); assert(0 <= idx2 && idx2 < f_tree[idx].n); f_tree[idx].update(idx2, d); } } // get sum of values < v where idx < idx T query(int32_t idx, int64_t v) { assert(0 <= idx && idx <= n); T res = BIT::UNIT; for (; idx > 0; idx -= (idx & -idx)) { auto idx2 = lookup(vals[idx], v); T sub = f_tree[idx].query(idx2); res = f(res, sub); } return res; } }; // L, R, INTERCEPT, TYPE using Wiggle = std::array; // count the number of pairs of wiggles that do not intersect int64_t solve(std::span wiggles) { // l1 < l2 && (r1 < l2 || (t1 == t2 && r1 < r2 && i1 < i2)) std::vector xs; xs.reserve(2 * wiggles.size()); for (auto [l, r, i, t] : wiggles) { xs.push_back(l); xs.push_back(r); } xs = compress(xs); std::array, 2> ds{xs.size(), xs.size()}; using Event = std::array; std::vector, 2>> events(xs.size()); for (auto [l, r, i, t] : wiggles) { int64_t lidx = lookup(xs, l); int64_t ridx = lookup(xs, r); events[lidx][0].push_back({ridx, i, t}); events[ridx][1].push_back({ridx, i, t}); for (auto& bit : ds) { bit.insert(ridx, i); } } for (auto& bit : ds) { bit.finalize(); } int64_t ans = 0; int64_t passed = 0; for (const auto& [adds, removes] : events) { for (auto [ridx, i, t] : adds) { ans += passed + ds[t].query(ridx, i); } for (auto [ridx, i, t] : adds) { ds[t].update(ridx, i, +1); } for (auto [ridx, i, t] : removes) { ++passed; ds[t].update(ridx, i, -1); } } return ans; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int64_t n; std::cin >> n; std::vector horizs, verts; horizs.reserve(n); verts.reserve(n); for (auto i = 0; i < n; ++i) { int64_t x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; x1 *= 2; y1 *= 2; x2 *= 2; y2 *= 2; int64_t dx = std::abs(x2 - x1); int64_t dy = std::abs(y2 - y1); if (dx == dy) { // always intersects with everything continue; } else if (dx < dy) { int64_t cy = (y1 + y2) / 2; int64_t l = cy - (dx / 2); int64_t r = cy + (dx / 2); if (x1 > x2) { std::swap(x1, x2); std::swap(y1, y2); } if (y1 > y2) { horizs.push_back({l, r, l - x1, 0}); } else { horizs.push_back({l, r, x2 + l, 1}); } } else { int64_t cx = (x1 + x2) / 2; int64_t l = cx - (dy / 2); int64_t r = cx + (dy / 2); if (y1 > y2) { std::swap(x1, x2); std::swap(y1, y2); } if (x1 > x2) { verts.push_back({l, r, l - y1, 0}); } else { verts.push_back({l, r, y2 + l, 1}); } } } int64_t ans = solve(horizs) + solve(verts); int64_t total = n * (n - 1) / 2; std::cout << (total - ans) << '\n'; return 0; }