การสะท้อนเส้นใน C++

สมมติว่ามี n จุดบนระนาบ 2 มิติ เราต้องตรวจสอบว่ามีเส้นที่ขนานกับแกน y ที่สะท้อนจุดที่กำหนดอย่างสมมาตรหรือไม่ กล่าวอีกนัยหนึ่ง ตรวจสอบว่ามีเส้นที่หลังจากสะท้อนจุดทั้งหมดผ่านเส้นนั้น เซตของจุดต้นฉบับจะเหมือนกับเซตของจุดที่ถูกสะท้อน

เช่น ถ้าอินพุทเป็น points = [[1,1],[-1,1]]

ผลลัพธ์จะเป็น true

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −

• กำหนดเซต ok

• n := ขนาดของ points

• minVal := infinity

• maxVal := -infinity

• ลูป i := 0 ถึง n-1 ทำ −

  • minVal := min ของ minVal และ points[i][0]

  • maxVal := max ของ maxVal และ points[i][0]

  • แทรก points[i] ลงใน ok

• mid := maxVal + minVal

• ลูป i := 0 ถึง n-1 ทำ −

  • x := points[i][0]

  • y := points[i][1]

  • x := mid - x

  • ถ้า { x, y } ไม่อยู่ใน ok แล้ว −

    • คืนค่า false

• คืนค่า true

ตัวอย่าง

ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −

#include <bits/stdc++.h> using namespace std; class Solution { public:    bool isReflected(vector<vector<int>>& points) {       set<vector<int> > ok;       int n = points.size();       int minVal = INT_MAX;       int maxVal = INT_MIN;       for (int i = 0; i < n; i++) {          minVal = min(minVal, points[i][0]);          maxVal = max(maxVal, points[i][0]);          ok.insert(points[i]);       }       int mid = maxVal + minVal;       for (int i = 0; i < n; i++) {          int x = points[i][0];          int y = points[i][1];          x = mid - x;          if (!ok.count({ x, y }))             return false;       }       return true;    } }; main(){    Solution ob;    vector<vector<int>> v = {{1,1},{-1,1}};    cout << (ob.isReflected(v)); }

อินพุท

{{1,1},{-1,1}}

เอาต์พุท

1