पायथन में एक रेखा पर स्थित बिंदुओं की अधिकतम संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास निर्देशांकों की एक सूची है। प्रत्येक निर्देशांक में दो मान x और y होते हैं, जो कार्तीय तल पर एक बिंदु दर्शाते हैं। अब उस रेखा पर स्थित अधिकतम बिंदुओं की संख्या ज्ञात करें।

उदाहरण के लिए, यदि इनपुट है coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]], तो आउटपुट 4 होगा, क्योंकि बिंदु [1, 1], [2, 2], [6, 6], [7, 7] एक रेखा पर स्थित हैं।

एल्गोरिदम

• res := 0
• प्रत्येक बिंदु i के लिए:
  • (x1, y1) := points[i]
  • slopes := नया मैप, same := 1
  • प्रत्येक बिंदु j > i के लिए:
    • (x2, y2) := points[j]
    • यदि x2 == x1, तो slopes[inf]++
    • अन्यथा यदि x1 == x2 और y1 == y2, तो same++
    • अन्यथा, slope = (y2-y1)/(x2-x1) की गणना करें और slopes[slope]++
  • यदि slopes खाली नहीं है, तो res = max(res, same + max(slopes.values()))
• res वापस करें

उदाहरण

class Solution:
    def solve(self, points):
        res = 0
        for i in range(len(points)):
            x1, y1 = points[i][0], points[i][1]
            slopes = {}
            same = 1
            for j in range(i + 1, len(points)):
                x2, y2 = points[j][0], points[j][1]
                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()))
        return res

ob = Solution()
coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
print(ob.solve(coordinates))

इनपुट

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

आउटपुट

4