คะแนนสูงสุดในบรรทัดใน C++

สมมุติว่าเรามีเครื่องบิน 2 มิติ เราต้องหาจำนวนจุดที่อยู่บนเส้นตรงเดียวกันมากที่สุด ดังนั้นหากคะแนนเป็นเช่น −

แล้วมี 4 จุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=จำนวนแต้ม ถ้า n <3 ให้คืนค่า n

• ตอบ :=2

• สำหรับผมอยู่ในช่วง 1 ถึง n – 1

  • นับ :=0

  • เอาสองจุดจากดัชนี i และ i – 1 นี่คือ p1, p2

  • ถ้าจุด p1 และ p2 เท่ากัน

    • สำหรับ j ในช่วง 0 ถึง n – 1

      • ถ้า points[j].x =p1.x และ points[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

  • 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