#include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back typedef long long ll; typedef long double ld; typedef vector vi; struct FT { vector s; FT(int n) : s(n) {} void update(int pos, ll dif) { // a[pos] += dif for (; pos < sz(s); 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; } int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum // Returns n if no sum is >= sum, or -1 if empty sum is. if (sum <= 0) return -1; int pos = 0; for (int pw = 1 << 25; pw; pw >>= 1) { if (pos + pw <= sz(s) && s[pos + pw-1] < sum) pos += pw, sum -= s[pos-1]; } return pos; } }; struct FT2 { vector ys; vector ft; FT2(int limx) : ys(limx) {} void fakeUpdate(int x, int y) { for (; x < sz(ys); x |= x + 1) ys[x].pb(y); } void init() { for (vi& v : ys) sort(all(v)), ft.emplace_back(sz(v)); } int ind(int x, int y) { return (int)(lower_bound(all(ys[x]), y) - ys[x].begin()); } void update(int x, int y, ll dif) { for (; x < sz(ys); 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; } }; struct P { ll x, y; P(ll _x=0, ll _y=0) : x(_x), y(_y) {} bool operator<(P p) { return pair{x, y} < pair{p.x, p.y}; }; friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; typedef pair info; info get(info a) { auto [l, r] = a; ll dy = r.y-l.y; ll dx = r.x-l.x; assert(dx >= 0); assert(dx >= abs(dy)); assert(dx%2==0); assert(dy%2==0); ll m = l.x+dx/2; return {P(m-dy/2, r.y), P(m+dy/2, l.y)}; } pair slope(info a) { auto [u, _] = a; return {u.y+u.x, u.y}; } ll go1(vector& a, vector& b) { vector> events; auto add = [&events](vector& ps, int id) { for(auto p : ps) { auto [u, v] = get(p); if(u.x > v.x) swap(u, v); events.pb({u.x, -id}); events.pb({v.x, id}); } }; add(a, 1); add(b, 2); sort(all(events)); ll res = 0; vector seen(2); for(auto [_, e] : events) { int id = abs(e)-1; if(e < 0) { seen[id]++; res += seen[id^1]; } else { seen[id]--; } } return res; } ll go2(vector& v) { int n = sz(v); vector coords; for(int i = 0; i < n; i++) { v[i] = get(v[i]); coords.pb(v[i].first.x); coords.pb(v[i].second.x); } sort(all(coords)); coords.erase(unique(all(coords)), coords.end()); auto comp = [&](ll val) { return (int)(lower_bound(all(coords), val)-coords.begin()); }; sort(all(v), [](info a, info b) { return slope(a) < slope(b); }); ll res = 0; FT2 tree(sz(coords)+1); for(int i = 0; i < n; i++) { int l = comp(v[i].first.x); int r = comp(v[i].second.x); tree.fakeUpdate(l, r); } tree.init(); for(int i = 0; i < n; i++) { int l = comp(v[i].first.x); int r = comp(v[i].second.x); //[0, l-1], [r, n] res += tree.query(l, sz(coords))-tree.query(l, r); //[l, r], [0, n] res += tree.query(r+1, sz(coords))-tree.query(l, sz(coords)); tree.update(l, r, 1); } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; ll boxes = 0, horz = 0, vert = 0; vector hUp, hDown, vUp, vDown; for(int i = 0; i < n; i++) { P u, v; cin >> u.x >> u.y >> v.x >> v.y; u.x *= 2; u.y *= 2; v.x *= 2; v.y *= 2; if(v < u) swap(u, v); ll dx = v.x-u.x; ll dy = v.y-u.y; //square if(dx == abs(dy)) { boxes++; } //vert else if(dx > abs(dy)) { vert++; if(dy > 0) vUp.pb({u, v}); else vDown.pb({u, v}); } //horz else { horz++; swap(u.x, u.y); swap(v.x, v.y); if(v < u) swap(u, v); dx = v.x-u.x; dy = v.y-u.y; if(dy > 0) hUp.pb({u, v}); else hDown.pb({u, v}); } } ll ans = 0; ans += boxes*(boxes-1)/2; ans += boxes*(horz+vert); ans += horz*vert; auto rev = [](vector& v) { for(int i = 0; i < sz(v); i++) { v[i].first.x *= -1; v[i].second.x *= -1; swap(v[i].first, v[i].second); } }; ans += go1(vUp, vDown); ans += go1(hUp, hDown); ans += go2(vUp); rev(vDown); ans += go2(vDown); ans += go2(hUp); rev(hDown); ans += go2(hDown); cout << ans << "\n"; }