11639 Guard the Land

題目連結

題目翻譯

農夫 Latif 有一塊 100×100 公尺的矩形農地，每晚他雇兩個警衛分別看守一個矩形區域。

• 強安全：兩個警衛都覆蓋到的區域
• 弱安全：只有一個警衛覆蓋到的區域
• 不安全：兩個警衛都沒覆蓋到的區域

給你兩個矩形的座標，計算三種區域各自的面積（單位：m²）。

輸入

第一行測資數 N（N ≤ 100），接下來 N 組，每組兩行，每行四個整數 x1 y1 x2 y2，分別是矩形左下角和右上角座標（0 ≤ 座標 ≤ 100）。

輸出

每組輸出 Night t: A B C，A 是強安全面積，B 是弱安全面積，C 是不安全面積。

解題思路

設兩個矩形面積分別為 a、b，兩者交集面積為 c：

• 強安全 = c（兩個都覆蓋）
• 弱安全 = a + b − 2c（各自有覆蓋但對方沒有，即 (a−c) + (b−c)）
• 不安全 = 10000 − a − b + c（總面積 − 聯集面積，聯集 = a + b − c）

交集寬度：max(0, min(x2,x4) − max(x1,x3))，高度同理，相乘得 c。

程式碼

//author: Piau
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

signed main() { WA();
    int t = 1, T;
    for (cin >> T; t <= T; t++) {
        cout << "Night " << t << ": ";
        int x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        int a = (x2 - x1) * (y2 - y1);
        int b = (x4 - x3) * (y4 - y3);
        int c = max(0LL, min(x2, x4) - max(x1, x3)) * max(0LL, min(y2, y4) - max(y1, y3));
        cout << c << ' ' << a+b-2*c << ' ' << 10000-a-b+c << '\n';
    }
}