C++ में एक रेखा पर अधिकतम बिंदु

मान लीजिए हमारे पास एक 2D तल है। हमें उन अधिकतम बिंदुओं की संख्या ढूंढनी है जो एक ही सीधी रेखा पर स्थित हैं। तो यदि बिंदु इस तरह हैं -

तो 4 बिंदु हैं

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• n := बिंदुओं की संख्या, यदि n < 3, तो n लौटाएं

• ans := 2

• i को 1 से n - 1 तक की रेंज में

  • count := 0

  • इंडेक्स i और i - 1 से दो बिंदु लें, ये p1, p2 हैं

  • यदि p1 और p2 बिंदु समान हैं, तो

    • j को 0 से n - 1 तक की रेंज में

      • यदि points[j].x = p1.x और points[j].y = p1.y, तो count को 1 से बढ़ाएं

  • अन्यथा -

    • j को 0 से n - 1 तक की रेंज में

      • p3 := इंडेक्स j से बिंदु

      • यदि p3.y - p2.y * p2.x - p1.x = p2.y - p1.y * p3.x - p2.x, तो count को 1 से बढ़ाएं

  • ans := ans और count का अधिकतम

• ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#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];          lli x2 = points[i][0];          lli y1 = points[i-1][1];          lli 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];                int y3 = points[j][1];                if((y3-y2)*(x2-x1) == (y2-y1)*(x3-x2))count++ ;             }          }          ans = max(ans, count);       }       return ans;    } }; main(){    Solution ob;    vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};    cout << (ob.maxPoints(v)); }

इनपुट

[{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]

आउटपुट

4