โปรแกรมนับจุดที่อยู่บนเส้นตรงเดียวกันใน Python

ได้รับรายการพิกัด [[x, y], ...] ต้องหาจำนวนจุดสูงสุดที่อยู่บนเส้นตรงเดียวกัน

ตัวอย่าง

Input: [[6,2],[8,3],[10,4],[1,1],[2,2],[6,6],[7,7]]

Output: 4 (จุด [1,1], [2,2], [6,6], [7,7] อยู่บนเส้น y = x)

แนวทางแก้ปัญหา

ใช้ Hash Map นับความชัน (Slope) สำหรับแต่ละจุดฐาน:

1. เลือกจุด i เป็นฐาน
2. คำนวณความชันกับจุดอื่นๆ ทั้งหมด j > i
   • แนวตั้ง (x เท่ากัน) → ใช้ float('inf') แทนความชัน
   • จุดซ้ำกัน → นับแยกในตัวแปร same
   • ทั่วไป → slope = (y2-y1)/(x2-x1)
3. หาความชันที่พบบ่อยที่สุด → max_count = same + max(slope_counts)
4. อัปเดตคำตอบทั่วไป

การใช้งาน (Python)

class Solution:
    def solve(self, points):
        res = 0
        n = len(points)
        
        for i in range(n):
            x1, y1 = points[i]
            slopes = {}
            same = 1
            
            for j in range(i + 1, n):
                x2, y2 = points[j]
                
                if x2 == x1:
                    slopes[float('inf')] = slopes.get(float('inf'), 0) + 1
                elif x1 == x2 and y1 == y2:
                    same += 1
                else:
                    slope = (y2 - y1) / (x2 - x1)
                    slopes[slope] = slopes.get(slope, 0) + 1
            
            if slopes:
                res = max(res, same + max(slopes.values()))
            else:
                res = max(res, same)
        
        return res

# ทดสอบ
ob = Solution()
coordinates = [[6,2],[8,3],[10,4],[1,1],[2,2],[6,6],[7,7]]
print(ob.solve(coordinates))  # Output: 4

หมายเหตุ

การใช้ float อาจมีปัญหาความแม่นยำ สำหรับการใช้งานจริงควรใช้ Fraction หรือเก็บเป็นคู่ (dy, dx) ลดรูปด้วย GCD