#define ENABLE_DEBUG 0 // Kana's kitchen {{{ #include #define ALL(v) std::begin(v),std::end(v) #define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++) using i32 = std::int_least32_t; using i64 = std::int_least64_t; using u32 = std::uint_least32_t; using u64 = std::uint_least64_t; using usize = std::size_t; template using pair = std::pair; template using diag_pair = std::pair; template using tuple = std::tuple; template using vec = std::vector; template using numr = std::numeric_limits; #ifdef NGTKANA #include #else #define DEBUG(...)(void)0 #endif /*}}}*/ i64 inf = 40'000; struct stairs { std::map> map; stairs() : map({{0, inf}, {inf, 0}}) {} i64 add(i64 x, i64 y) { DEBUG(map, x, y); auto lb = map.lower_bound(x); assert(lb!=map.begin() && lb!=map.end()); if (y < std::prev(lb)->second) return 0; DEBUG(x, y, *lb); i64 ans = 0; while (true) { auto [x0, y0] = *std::prev(lb); auto [x1, y1] = *lb; assert(x1 <= x && x < x0); assert(y0 < y1 && y0 <= y); DEBUG(*lb, *std::prev(lb), (x - x1) * (y - y0)); if (y < y1) { ans += (x - x1) * (y - y0); if (x1 < x && y0 < y) { map.emplace(x, y); } DEBUG(ans, map); return ans; } assert(lb!=map.end()); auto [x2, y2] = *std::next(lb); ans -= (x1 - x2) * (y1 - y0); lb = map.erase(lb); } } }; template = 0> auto mkvec(Args... args) { return T(args...); } template = 0> auto mkvec(usize sz, Args... args) { using value_type = std::decay_t(args...))>; return vec(sz, value_type(args...)); } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout << std::setprecision(15) << std::fixed; usize n; std::cin >> n; auto st = mkvec<2, stairs>(2, 2); while (n--) { vec x(2), y(2); std::cin >> x.at(0) >> y.at(0); std::cin >> x.at(1) >> y.at(1); x.at(0) = -x.at(0); y.at(0) = -y.at(0); i64 ans = 0; for (usize i=0; i<2; i++) { for (usize j=0 ;j<2; j++) { ans += st.at(i).at(j).add(x.at(i), y.at(j)); } } std::cout << ans << '\n'; } } /* * 第一象限のみを考えましょう。 * x 座標が単調増加、y 座標が単調減少だと思います。(実際には x の降順の map です。) * * (a, b) が入力されました。 * x <= a なる最大の x を取ります。(lower_bound) * 初回だけは、埋没チェックです。一つ右の y 座標以下だった場合は、何もしません。 * * さて、とりあえず (x - a) * (y - b) を足しましょう。 * b <= y ならば、自分が消えればみんな幸せになるので、それで † 終わり † にしましょう。 * y < b ならば、(x, y) を消して、次を見ましょう。 */