แนวคิด
ในส่วนที่เกี่ยวกับจุดคู่ 'n' ที่ให้มา ภารกิจของเราคือกำหนดจุดสี่จุดเพื่อให้เป็นรูปสี่เหลี่ยมจัตุรัสที่มีด้านขนานกับแกน x และ y มิฉะนั้นจะแสดง "ไม่มีสี่เหลี่ยมจัตุรัสดังกล่าว" ควรสังเกตว่าถ้ามีช่องสี่เหลี่ยมมากกว่าหนึ่งช่อง ให้เลือกช่องที่มีพื้นที่สูงสุด
อินพุต
n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)
ผลลัพธ์
Side of the square is: 3, points of the square are 2, 2 5, 2 2, 5 5, 5
คำอธิบาย
จุด 2, 2 5, 2 2, 5 5, 5 เป็นรูปสี่เหลี่ยมจัตุรัสด้าน 3
อินพุต
n= 6, points= (2, 2), (5, 6), (4, 5), (5, 4), (8, 5), (4, 2)
ผลลัพธ์
No such square
วิธีการ
วิธีง่ายๆ − เลือกคู่ของจุดที่เป็นไปได้ทั้งหมดที่มีสี่ลูปซ้อนกัน จากนั้นตรวจสอบว่าจุดนั้นเป็นรูปสี่เหลี่ยมจัตุรัสซึ่งขนานกับแกนหลักหรือไม่ จะเห็นได้ว่าถ้าใช่ ให้ตรวจสอบว่าเป็นสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดในแง่ของพื้นที่หรือไม่ และเก็บผลลัพธ์ จากนั้นพิมพ์ผลลัพธ์ที่ส่วนท้ายของโปรแกรม
ความซับซ้อนของเวลา - O(N^4)
วิธีที่มีประสิทธิภาพ − สร้างการวนซ้ำซ้อนสำหรับมุมบนขวาและมุมล่างซ้ายของสี่เหลี่ยม และสร้างสี่เหลี่ยมจัตุรัสที่มีจุดสองจุดนั้น จากนั้นตรวจสอบว่าจุดอีกสองจุดที่ถือว่ามีอยู่จริงหรือไม่ ตอนนี้เพื่อตรวจสอบว่ามีจุดอยู่หรือไม่ ให้สร้างแผนที่และจัดเก็บจุดในแผนที่เพื่อลดเวลาในการตรวจสอบว่าจุดนั้นมีอยู่จริง นอกจากนี้ ให้ตรวจสอบสี่เหลี่ยมที่ใหญ่ที่สุดตามพื้นที่จนถึงตอนนี้และแสดงในตอนท้าย
ตัวอย่าง
// C++ implemenataion of the above approach
#include <bits/stdc++.h>
using namespace std;
// Determine the largest square
void findLargestSquare1(long long int points1[][2], int n1){
// Used to map to store which points exist
map<pair<long long int, long long int>, int> m1;
// mark the available points
for (int i = 0; i < n1; i++) {
m1[make_pair(points1[i][0], points1[i][1])]++;
}
long long int side1 = -1, x1 = -1, y1 = -1;
// Shows a nested loop to choose the opposite corners of square
for (int i = 0; i < n1; i++) {
// Used to remove the chosen point
m1[make_pair(points1[i][0], points1[i][1])]--;
for (int j = 0; j < n1; j++) {
// Used to remove the chosen point
m1[make_pair(points1[j][0], points1[j][1])]--;
// Verify if the other two points exist
if (i != j && (points1[i][0]-points1[j][0]) == (points1[i][1]-points1[j][1])){
if (m1[make_pair(points1[i][0], points1[j][1])] > 0
&& m1[make_pair(points1[j][0], points1[i][1])] > 0) {
// So if the square is largest then store it
if (side1 < abs(points1[i][0] - points1[j][0])
|| (side1 == abs(points1[i][0] -points1[j][0])
&& ((points1[i][0] * points1[i][0]+ points1[i][1] * points1[i][1])
< (x1 * x1 + y1 * y1)))) {
x1 = points1[i][0];
y1 = points1[i][1];
side1 = abs(points1[i][0] - points1[j][0]);
}
}
}
// Used to add the removed point
m1[make_pair(points1[j][0], points1[j][1])]++;
}
// Used to add the removed point
m1[make_pair(points1[i][0], points1[i][1])]++;
}
// Used to display the largest square
if (side1 != -1)
cout << "Side of the square is : " << side1
<< ", \npoints of the square are " << x1 << ", " << y1<< " "<< (x1 + side1) << ", " << y1
<< " "
<< (x1) << ", " << (y1 + side1)
<< " "
<< (x1 + side1) << ", " << (y1 + side1) << endl;
else
cout << "No such square" << endl;
}
//Driver code
int main(){
int n1 = 6;
// given points
long long int points1[n1][2]= { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 }};
// Determine the largest square
findLargestSquare1(points1, n1);
return 0;
} ผลลัพธ์
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5
