#pragma comment (linker, "/STACK:1073741824") #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define SZ(x) (int((x).size())) #define FOR(i, a, b) for(int (i) = (a); (i) <= (b); ++(i)) #define ROF(i, a, b) for(int (i) = (a); (i) >= (b); --(i)) #define REP(i, n) for (int (i) = 0; (i) < (n); ++(i)) #define REPD(i, n) for (int (i) = (n); (i)--; ) #define FE(i, a) for (int (i) = 0; (i) < (int((a).size())); ++(i)) #define MEM(a, val) memset((a), val, sizeof(a)) #define INF 1000000000 #define LLINF 1000000000000000000LL #define PB push_back #define PPB pop_back #define ALL(c) (c).begin(), (c).end() #define SQR(a) ((a)*(a)) #define MP(a,b) make_pair((a), (b)) #define XX first #define YY second #define GET_RUNTIME_ERROR *(int*)(NULL) = 1 #define ASSERT_GE(a, b) if (a < b) {\ cerr << fixed << setprecision(16); \ cerr << "ASSERT_GE failed: " << a << " vs " << b << endl; \ cerr << "Difference is " << (a - b) << endl; \ assert(false); \ } typedef vector vint; typedef vector vLL; typedef double dbl; typedef long double ldbl; typedef vector > vpii; typedef long long LL; typedef pair pii; // Class for Fenwick tree. class Fenwick { vector f; public: Fenwick(int n) { f.assign(n, 0); } void upd(int i, int val) { for (; i < f.size(); i |= i + 1) f[i] += val; } int get(int i) const { int res = 0; for (; i >= 0; i = (i & (i + 1)) - 1) { res += f[i]; } return res; } }; // Struct to store lines. struct Line { int x1, y1, x2, y2; int answer; int idx; Line(int x1__, int y1__, int x2__, int y2__, int idx__) : x1(x1__), y1(y1__), x2(x2__), y2(y2__), answer(0), idx(idx__) { if (IsVertical()) { if (y1 > y2) swap(y1, y2); } else if (IsHorizontal()) { if (x1 > x2) swap(x1, x2); } } bool IsVertical() const { return x1 == x2; } bool IsHorizontal() const { return y1 == y2; } string toString() const { static char s[100]; sprintf(s, "[(%d, %d); (%d, %d)]", x1, y1, x2, y2); return s; } }; // For horizontal/vertical lines solve only for vertical. void solve(vector& horizontal, vector& vertical) { vector, Line*>> events; vector> endpoints; endpoints.reserve(horizontal.size()*2); //cerr << horizontal.size() << endl; //cerr << vertical.size() << endl; for (Line& line : horizontal) { events.emplace_back(MP(line.x1, -1), &line); events.emplace_back(MP(line.x2, +1), &line); endpoints.push_back(make_pair(line.x1, line.y1)); endpoints.push_back(make_pair(line.x2, line.y2)); } for (Line& line : vertical) { events.emplace_back(MP(line.x1, 0), &line); } sort(endpoints.begin(), endpoints.end()); auto cnt = [&endpoints](int x, int y) { auto it = lower_bound(endpoints.begin(), endpoints.end(), make_pair(x, y)); int v = (int)(it != endpoints.end() && *it == make_pair(x, y)); return v; }; Fenwick f(100100); sort(ALL(events)); for (auto& event : events) { //cerr << event.first.first << " " << event.first.second << " " << event.second->toString() << endl; } int decreased = 0; for (auto& event : events) { int type = event.first.second; Line& line = *event.second; if (type == -1) { f.upd(line.y1, +1); } else if (type == 0) { line.answer = f.get(line.y2) - f.get(line.y1 - 1); int v = line.answer; line.answer -= cnt(line.x1, line.y1); line.answer -= cnt(line.x2, line.y2); if (line.answer != v) { decreased += v - line.answer; } } else if (type == 1) { f.upd(line.y2, -1); } } cerr << "decreased " << decreased << endl; } // Solves the test. void solve() { int n; scanf("%d", &n); vector horizontal; vector vertical; REP(i, n) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); Line line(x1, y1, x2, y2, i); if (line.IsHorizontal()) { horizontal.push_back(line); } else if (line.IsVertical()) { vertical.push_back(line); } else { cerr << i << endl; assert(false); } } // For horizontal/vertical lines solve only for vertical. solve(horizontal, vertical); for (Line& line : horizontal) { swap(line.x1, line.y1); swap(line.x2, line.y2); } for (Line& line : vertical) { swap(line.x1, line.y1); swap(line.x2, line.y2); } // For horizontal/vertical lines solve only for horizontal. solve(vertical, horizontal); vector ans(n); for (Line& line : horizontal) ans[line.idx] = line.answer; for (Line& line : vertical) ans[line.idx] = line.answer; LL sum = 0; for (int i = 0; i < ans.size(); ++i) { sum += ans[i]; } cout << sum / 2 << endl; for (int i = 0; i < ans.size(); ++i) { printf("%d%c", ans[i], i + 1 == ans.size() ? '\n' : ' '); } } int main() { ios_base::sync_with_stdio(false); int t = 1; //scanf("%d", &t); while(t--) { solve(); } return 0; }