เราได้รับสี่เหลี่ยมผืนผ้าที่มีขนาดความสูง (height) × ความกว้าง (width) โดยมุมซ้ายล่างอยู่ที่จุดกำเนิด (0,0) เป้าหมายคือการนับจำนวนรูปสี่เหลี่ยมขนมเปียกปูน (Rhombus) ที่อยู่ภายในสี่เหลี่ยมผืนผ้า และตรงตามเงื่อนไขต่อไปนี้:
- พื้นที่มากกว่า 0
- เส้นทแยงมุมขนานกับแกน x และแกน y
- มุมทั้ง 4 มุมมีพิกัดเป็นจำนวนเต็ม
ตัวอย่าง
อินพุต: length = 3, width = 3
เอาต์พุต: 4
คำอธิบาย: รูปสี่เหลี่ยมขนมเปียกปูน 4 รูปคือ:
1. [(1,0), (2,1), (1,2), (0,1)] 2. [(2,0), (3,1), (2,2), (1,1)] 3. [(2,1), (3,2), (2,3), (1,2)] 4. [(1,1), (2,1), (1,2), (0,1)]
อินพุต: length = 2, width = 3
เอาต์พุต: 2
แนวทางการแก้ปัญหา
รูปสี่เหลี่ยมขนมเปียกปูนแรกที่มีพื้นที่ > 0 และพิกัดเป็นจำนวนเต็ม จะเริ่มจากมุมขวาบนที่ (2,2) วนลูปจาก i=j=2 ถึง i≤length และ j≤width โดยเพิ่มทีละ 2 (เพื่อให้พิกัดเป็นจำนวนเต็ม) จำนวนรูปสี่เหลี่ยมขนมเปียกปูนที่มีเส้นทแยงมุมยาว i และ j จะเท่ากับ (height - i + 1) × (width - j + 1)
การนำไปใช้ (Implementation)
#include <bits/stdc++.h>
using namespace std;
long long possible_rhombus(int height, int width) {
long long count = 0;
for (int i = 2; i <= height; i += 2) {
for (int j = 2; j <= width; j += 2) {
int temp_1 = height - i + 1;
int temp_2 = width - j + 1;
count += temp_1 * temp_2;
}
}
return count;
}
int main() {
int height = 4, width = 4;
cout << "Count of number of rhombi possible inside a rectangle of given size are: " << possible_rhombus(height, width);
return 0;
}
เอาต์พุต
Count of number of rhombi possible inside a rectangle of given size are: 16
