C++ এ একটি লাইনে সর্বোচ্চ পয়েন্ট

ধরুন আমাদের একটি 2D প্লেন আছে। একই সরলরেখায় অবস্থানকারী বিন্দুর সর্বোচ্চ সংখ্যা আমাদের খুঁজে বের করতে হবে। তাই যদি পয়েন্ট −

তারপর 4 পয়েন্ট আছে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=বিন্দুর সংখ্যা, যদি n <3 হয়, তাহলে n

  ফেরত দিন

• উত্তর :=2

• 1 থেকে n – 1

  রেঞ্জের জন্য i

  • গণনা :=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