แนวคิด
ได้รับคู่จุด 'n' คู่ ให้หาจุด 4 จุดที่สร้างเป็นสี่เหลี่ยมจัตุรัสซึ่งด้านขนานกับแกน x และ y มิฉะนั้นแสดง "No such square" หากมีหลายสี่เหลี่ยม ให้เลือกที่มีพื้นที่มากที่สุด
อินพุต
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
วิธีการ
วิธีง่าย - เลือกคู่จุดทั้งหมดที่เป็นไปได้ด้วยลูปซ้อน 4 ชั้น แล้วตรวจสอบว่าจุดเหล่านั้นสร้างสี่เหลี่ยมจัตุรัสขนานกับแกนหลักหรือไม่ หากใช่ ตรวจสอบว่ามันเป็นสี่เหลี่ยมที่ใหญ่ที่สุดในพื้นที่และเก็บผลลัพธ์ แล้วพิมพ์ผลลัพธ์ท้ายโปรแกรม
Time Complexity - O(N^4)
วิธีที่มีประสิทธิภาพ - สร้างลูปซ้อนสำหรับมุมบนขวาและมุมล่างซ้ายของสี่เหลี่ยม สร้างสี่เหลี่ยมด้วยจุดทั้งสองนี้ แล้วตรวจสอบว่าจุดอีกสองจุดที่สมมติมีอยู่จริงหรือไม่ โดยใช้ map เก็บจุดเพื่อลดเวลาตรวจสอบ นอกจากนี้ ตรวจสอบสี่เหลี่ยมที่ใหญ่ที่สุดตามพื้นที่และแสดงผลท้ายสุด
ตัวอย่างโค้ด C++
// การนำไปใช้ C++ ของวิธีการข้างต้น
#include <bits/stdc++.h>
using namespace std;
// หาสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุด
void findLargestSquare1(long long int points1[][2], int n1) {
// ใช้ map เก็บจุดที่มีอยู่
map<pair<long long int, long long int>, int> m1;
// ทำเครื่องหมายจุดที่มี
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;
// ลูปซ้อนเลือกมุมตรงข้ามของสี่เหลี่ยม
for (int i = 0; i < n1; i++) {
// ลบจุดที่เลือกออก
m1[make_pair(points1[i][0], points1[i][1])]--;
for (int j = 0; j < n1; j++) {
// ลบจุดที่เลือกออก
m1[make_pair(points1[j][0], points1[j][1])]--;
// ตรวจสอบว่าจุดอีกสองจุดมีอยู่หรือไม่
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) {
// ถ้าสี่เหลี่ยมใหญ่กว่าให้เก็บไว้
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]);
}
}
}
// เพิ่มจุดที่ลบออกกลับเข้าไป
m1[make_pair(points1[j][0], points1[j][1])]++;
}
// เพิ่มจุดที่ลบออกกลับเข้าไป
m1[make_pair(points1[i][0], points1[i][1])]++;
}
// แสดงสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุด
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;
}
// โค้ดหลัก
int main() {
int n1 = 6;
// จุดที่กำหนด
long long int points1[n1][2] = {{2, 2}, {5, 5}, {4, 5}, {5, 4}, {2, 5}, {5, 2}};
// หาสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุด
findLargestSquare1(points1, n1);
return 0;
}
เอาต์พุต
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5
