#include #include using namespace std; typedef long long ll; typedef long double ld; // add some black magic for faster hash sets #include using namespace __gnu_pbds; const ll INF = 2e9+1; int n; ll ans=0; typedef array twr; typedef pair pt; vector towers; ostream& operator<<(ostream &o,const pt &p) { return o<<"("<("< hor, ver; // horizontal and verticals struct BITree { int N = 0; vector> vals; vector> bit; gp_hash_table ridx; /** @return the first index i such that v[i] <= x */ int ind(const vector &v, int x) { return upper_bound(begin(v), end(v), x) - begin(v) - 1; } BITree(vector> &todo) { sort(begin(todo), end(todo), [](const array &a, const array &b) -> bool { return a[1] < b[1]; }); vector coords; for (auto [r, c] : todo) { coords.push_back(r); coords.push_back(c); } coords.push_back(-INF-1); coords.push_back(INF+1); sort(coords.begin(), coords.end()); for(int x: coords) { if (!coords.empty() && x==coords.back()) continue; ridx[x] = N++; } vals.resize(N + 1); bit.resize(N + 1); for (auto&[r, c] : todo) { r = ridx[r]; c = ridx[c]; } for (int i = 1; i <= N; i++) { vals[i].push_back(0); } for (auto [r, c] : todo) { r++, c++; for (; r <= N; r += r & -r) { if (vals[r].back() != c) { vals[r].push_back(c); } } } for (int i = 1; i <= N; i++) { bit[i].resize(vals[i].size()); } } void add(int r, int c, int val=1) { r = ridx[r], c = ridx[c]; r++, c++; for (; r <= N; r += r & -r) { int i = ind(vals[r], c); for (; i < (int)bit[r].size(); i += i & -i) { bit[r][i] += val; } } } /** @returns sum of points with row in [0, r] and column in [0, c] */ int query(int r, int c) { r++, c++; int sum = 0; for (; r > 0; r -= r & -r) { int i = ind(vals[r], c); for (; i > 0; i -= i & -i) { sum += bit[r][i]; } } return sum; } ll query_range(int xl, int xr, int yl, int yr) { return query(xr, yr) - query(xl-1, yr) - query (xr, yl-1) + query(xl-1, yl-1); } ll intersect(int l, int r) { l = ridx[l]; r = ridx[r]; return query_range(1,l-1, l, N) + query_range(1, r, r+1, N) + query_range(l, r, l, r) - query_range(1, l-1, r+1, N); } ll noninter(int l, int r) { l = ridx[l]; r = ridx[r]; return query_range(l+1, r, r+1, N); } }; void solve_cross(vector fw) { // assume all are / <- ll k = fw.size(); ll inter = 0; vector yinter(k); vector> todo; for(int i=0;i id(k); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int a, int b) { return yinter[a] < yinter[b]; }); auto flush = [&] (vector& idx) { for(int i: idx) { //cerr << "flush " << fw[i][1] << " " << fw[i][3] < cur; int last = -1; for(int i: id) { if (last != -1 && yinter[i] != yinter[last]) flush(cur); cur.push_back(i); last = i; } flush(cur); //cerr << "found inter " << inter < &ids) { //cerr << "number of lines " << ids.size() < fw, bk; vector coords; vector> qs; for(int i: ids) { int centerx = towers[i][0]/2 + towers[i][2]/2; int centery = towers[i][1]/2 + towers[i][3]/2; int dxdy = centerx - towers[i][0]; coords.push_back(centery+dxdy); coords.push_back(centery-dxdy); if (towers[i][1] > towers[i][3]) { twr t{towers[i][0], centery-dxdy, towers[i][2], centery+dxdy}; fw.push_back(t); qs.push_back({t[1], t[3]}); } else if (towers[i][1] < towers[i][3]) { twr t{towers[i][0], -(centery+dxdy), towers[i][2], -(centery-dxdy)}; bk.push_back(t); qs.push_back({-t[3], -t[1]}); } } BITree bt(qs); for(const auto &t: fw) { //cerr << "add " <> n; // handle square case by deleting immediately int real_n = n; for(int i=0;i> x1 >> y1 >> x2 >> y2; if (abs(x1-x2) == abs(y1-y2)) { ans += --real_n; } else { // make sure that x1 < x2 twr t{2*x1, 2*y1, 2*x2, 2*y2}; if (t[0] > t[2]) { swap(t[0], t[2]); swap(t[1], t[3]); } towers.emplace_back(t); if (abs(x1-x2) > abs(y1-y2)) { ver.push_back(towers.size()-1); } if (abs(x1-x2) < abs(y1-y2)) { hor.push_back(towers.size()-1); } } } n = real_n; // handle horizontal vs vertical ans+=(ll)hor.size() * (ll)ver.size(); // handle horizontal horizontal solve(hor); // handle vertical vertical for(int i=0;i t[3]) { towers[i] = {towers[i][3], towers[i][2], towers[i][1], towers[i][0]}; } else { towers[i] = {towers[i][1], towers[i][0], towers[i][3], towers[i][2]}; } } solve(ver); cout << ans <