सी ++ में एक लाइन पर मैक्स पॉइंट्स

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

फिर 4 अंक होते हैं

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

• n :=अंकों की संख्या, यदि n <3 है, तो n लौटाएं

• उत्तर :=2

• मैं के लिए 1 से n - 1 की सीमा में

  • गिनती :=0

  • सूचकांक i और i – 1 से दो बिंदु लें, ये p1, p2 हैं

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

    • j के लिए 0 से n - 1 की सीमा में

      • यदि अंक [j]। x =p1.x और अंक [j] .y =p1.y, तो 1 से गिनती बढ़ाएं

  • अन्यथा -

    • j के लिए 0 से n - 1 की सीमा में

      • p3 :=अनुक्रमणिका j से बिंदु

      • अगर p3.y - p2.y * p2.x - p1.x =p2.y - p1.y * p3.x - p2.x, तो 1 से गिनती बढ़ाएं

  • उत्तर :=अधिकतम उत्तर और गिनती

• वापसी उत्तर

उदाहरण

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

#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