โจทย์
หาพื้นที่รวมที่ถูกครอบคลุมโดยสี่เหลี่ยมสองรูปในระนาบ 2D โดยแต่ละรูปกำหนดโดยมุมซ้ายล่าง (A,B) และมุมขวาบน (C,D) สำหรับรูปแรก และ (E,F) (G,H) สำหรับรูปที่สอง
แนวคิดการแก้ปัญหา
พื้นที่รวม = พื้นที่รูปแรก + พื้นที่รูปที่สอง - พื้นที่ทับซ้อน (ถ้ามี)
ขั้นตอน
- ตรวจสอบว่าไม่ทับซ้อนกัน: ถ้า
C <= E || A >= G || B >= H || D <= F→ คืนค่าผลรวมพื้นที่ทั้งสองเลย - เก็บพิกัด x (A, C, E, G) ลงอาร์เรย์ h และพิกัด y (B, D, F, H) ลง v
- เรียงลำดับ h และ v
- พื้นที่ทับซ้อน =
(h[2] - h[1]) * (v[2] - v[1]) - พื้นที่รวม = พื้นที่รูป1 + พื้นที่รูป2 - พื้นที่ทับซ้อน
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
// ไม่ทับซ้อน
if (C <= E || A >= G || B >= H || D <= F)
return (C - A) * (D - B) + (G - E) * (H - F);
vector<int> h = {A, C, E, G};
vector<int> v = {B, D, F, H};
sort(h.begin(), h.end());
sort(v.begin(), v.end());
long long overlap = 1LL * (h[2] - h[1]) * (v[2] - v[1]);
long long total = 1LL * (C - A) * (D - B) + 1LL * (G - E) * (H - F);
return total - overlap;
}
};
int main() {
Solution ob;
cout << ob.computeArea(-3, 0, 3, 4, 0, -1, 9, 2); // 45
return 0;
}อินพุต / เอาต์พุต
Input: -3 0 3 4 0 -1 9 2
Output: 45
ความซับซ้อน
- Time: O(1) - การเรียง 4 ค่า คงที่
- Space: O(1)
