จุดสูงสุดบนเส้นตรงเดียวกันใน C++ (Max Points on a Line)

ภาพรวมปัญหา

ให้จุดบนระนาบ 2D หาจุดมากที่สุดที่อยู่บนเส้นตรงเดียวกัน

ตัวอย่าง

Points: (1,1), (3,2), (5,3), (4,1), (2,3), (1,4) → 4 จุด

วิธีแก้ปัญหา: O(N³) Brute Force (ตรวจสอบทุกคู่)

สำหรับแต่ละคู่จุด (i-1, i) หาจุดอื่นที่อยู่เส้นเดียวกัน
ใช้ cross product: (y3-y2)(x2-x1) == (y2-y1)(x3-x2)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n < 3) return n;
        int ans = 2;
        for (int i = 1; i < n; i++) {
            int count = 0;
            lli x1 = points[i-1][0], y1 = points[i-1][1];
            lli x2 = points[i][0], y2 = points[i][1];
            if (x1 == x2 && y1 == y2) {
                for (int j = 0; j < n; j++)
                    if (points[j][0] == x1 && points[j][1] == y1) count++;
            } else {
                for (int j = 0; j < n; j++) {
                    int x3 = points[j][0], y3 = points[j][1];
                    if ((y3-y2)*(x2-x1) == (y2-y1)*(x3-x2)) count++;
                }
            }
            ans = max(ans, count);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
    cout << (ob.maxPoints(v));
}

ผลลัพธ์

4

หมายเหตุ

วิธีนี้ O(N³) สำหรับ N ใหญ่ควรใช้ Hash Map เก็บ slope จากจุดฐาน (O(N² log N))