C++でのライン上の最大ポイント

2D平面があるとします。同じ直線上にある点の最大数を見つける必要があります。したがって、ポイントが次のような場合-

それから4つのポイントがあります

これを解決するには、次の手順に従います-

• n：=ポイントの数、n <3の場合、n

  を返します

• ans：=2

• 1からn–1の範囲のiの場合

  • カウント：=0

  • インデックスiとi– 1から2つのポイントを取ります。これらは、p1、p2

    です。

  • p1ポイントとp2ポイントが同じ場合、

    • 0からn–1の範囲のjの場合

      • points [j] .x=p1.xおよびpoints[j].y =p1.yの場合、カウントを1増やします

  • それ以外の場合-

    • 0からn–1の範囲のjの場合

      • p3：=インデックスjからのポイント

      • p3.y – p2.y * p2.x – p1.x =p2.y – p1.y * p3.x – p2.xの場合、カウントを1増やします

  • ans：=ansとカウントの最大値

• 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