#include using ll = long long; using interference_line_t = std::pair, std::pair>; std::pair convert_point(const std::pair &p) { return std::make_pair(p.first + p.second, p.first - p.second); } std::pair find_interference_range(std::pair p1, std::pair p2) { if (p1.first > p2.first) { std::swap(p1, p2); } int flags = 0; if (p1.first == p2.first || p1.second == p2.second) { flags |= 2; return std::make_pair( flags, std::pair, std::pair>{}); } if (p1.second > p2.second) { flags |= 1; } int mx = (p1.first + p2.first) / 2; int my = (p1.second + p2.second) / 2; int dx = std::abs(p1.first - p2.first); int dy = std::abs(p1.second - p2.second); auto line = std::make_pair(std::make_pair(mx, my), std::make_pair(mx, my)); int delta = std::abs(dy - dx) / 2; if (dx < dy) { line.first.first -= delta; line.second.first += delta; } else { line.first.second -= delta; line.second.second += delta; } return std::make_pair(flags, line); } ll count_non_overlap(std::vector> &segments) { for (auto &[s, e] : segments) { if (s > e) { std::swap(s, e); } } std::sort(segments.begin(), segments.end()); ll ret = 0; std::priority_queue, std::greater<>> pq; for (size_t i = 0; i < segments.size(); i++) { auto [s, e] = segments[i]; while (!pq.empty() && pq.top() < s) { pq.pop(); } ret += i - pq.size(); pq.push(e); } return ret; } struct FT { std::vector s; FT(int n) : s(n) {} void update(int pos, int dif) { // a[pos] += dif for (; pos < static_cast(s.size()); pos |= pos + 1) s[pos] += dif; } ll query(int pos) { // sum of values in [0, pos) ll res = 0; for (; pos > 0; pos &= pos - 1) res += s[pos - 1]; return res; } }; struct FT2 { std::vector> ys; std::vector ft; FT2(int limx) : ys(limx) {} void fakeUpdate(int x, int y) { for (; x < static_cast(ys.size()); x |= x + 1) ys[x].push_back(y); } void init() { for (std::vector &v : ys) sort(std::begin(v), std::end(v)), ft.emplace_back(static_cast(v.size())); } int ind(int x, int y) { return static_cast(lower_bound(std::begin(ys[x]), std::end(ys[x]), y) - ys[x].begin()); } void update(int x, int y, ll dif) { for (; x < static_cast(ys.size()); x |= x + 1) ft[x].update(ind(x, y), dif); } ll query(int x, int y) { ll sum = 0; for (; x; x &= x - 1) sum += ft[x - 1].query(ind(x - 1, y)); return sum; } }; void compress_coordinates(std::vector &lines) { std::sort(lines.begin(), lines.end()); lines.erase(std::unique(lines.begin(), lines.end()), lines.end()); } template ll count_non_intersect(std::vector lines) { if constexpr (!up) { for (auto &line : lines) { if (line.first.first != line.second.first) { std::swap(line.first, line.second); } line.first.first *= -1; line.second.first *= -1; } } std::vector line_group; for (const auto &[low, high] : lines) { line_group.push_back(low.second - low.first); line_group.push_back(high.second - high.first); } compress_coordinates(line_group); int num_coords = static_cast(line_group.size()); ll ret = 0; FT2 vertical_tree{num_coords + 1}, horizontal_tree{num_coords + 1}; std::vector xs, ys; for (const auto &[low, high] : lines) { int x = std::max(low.first, high.first), y = std::max(low.second, high.second); xs.push_back(x); ys.push_back(y); } compress_coordinates(xs); compress_coordinates(ys); std::vector>> horizontal_bucket(ys.size()), vertical_bucket(xs.size()), compressed_horizontal(ys.size()), compressed_vertical(xs.size()); for (const auto &[low, high] : lines) { int x = std::lower_bound(xs.begin(), xs.end(), std::max(low.first, high.first)) - xs.begin(), y = std::lower_bound(ys.begin(), ys.end(), std::max(low.second, high.second)) - ys.begin(); int low_line = std::lower_bound(line_group.begin(), line_group.end(), low.second - low.first) - line_group.begin(); int high_line = std::lower_bound(line_group.begin(), line_group.end(), high.second - high.first) - line_group.begin(); vertical_tree.fakeUpdate(low_line, high_line); horizontal_tree.fakeUpdate(low_line, high_line); if (low.first == high.first) { vertical_bucket[x].emplace_back(low_line, high_line); compressed_vertical[x].emplace_back(low.second, high.second); } else { horizontal_bucket[y].emplace_back(low_line, high_line); compressed_horizontal[y].emplace_back(low.first, high.first); } } horizontal_tree.init(); vertical_tree.init(); for (size_t x = 0; x < compressed_vertical.size(); x++) { ret += count_non_overlap(compressed_vertical[x]); for (const auto &[low, high] : vertical_bucket[x]) { ret += vertical_tree.query(low, low); ret += vertical_tree.query(num_coords, num_coords) - vertical_tree.query(num_coords, high + 1) - vertical_tree.query(low + 1, num_coords) + vertical_tree.query(low + 1, high + 1); } for (const auto &[low, high] : vertical_bucket[x]) { vertical_tree.update(low, high, 1); } } for (size_t y = 0; y < compressed_horizontal.size(); y++) { ret += count_non_overlap(compressed_horizontal[y]); for (const auto &[low, high] : horizontal_bucket[y]) { ret += horizontal_tree.query(low, high); ret += horizontal_tree.query(num_coords, num_coords) - horizontal_tree.query(num_coords, low + 1) - horizontal_tree.query(low + 1, num_coords) + horizontal_tree.query(low + 1, low + 1); ret += vertical_tree.query(high, high) + vertical_tree.query(num_coords, num_coords) - vertical_tree.query(num_coords, low + 1) - vertical_tree.query(low + 1, num_coords) + vertical_tree.query(low + 1, low + 1); } for (const auto &[low, high] : horizontal_bucket[y]) { horizontal_tree.update(low, high, 1); } } return ret; } int main() { int n; std::cin >> n; std::vector up, down; for (int i = 0; i < n; ++i) { std::pair p1, p2; std::cin >> p1.first >> p1.second; std::cin >> p2.first >> p2.second; p1.first *= 2, p1.second *= 2; p2.first *= 2, p2.second *= 2; p1 = convert_point(p1); p2 = convert_point(p2); auto [flags, line] = find_interference_range(p1, p2); if (flags & 2) { // ignore this tower, because all other tower will interfere with it at // some point continue; } if (flags & 1) { up.push_back(line); } else { down.push_back(line); } } ll num_non_intersect = count_non_intersect(up) + count_non_intersect(down); std::cout << (n * 1ll * (n - 1)) / 2 - num_non_intersect << '\n'; }