题解 | #直线上的牛#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param points int整型vector<vector<>> 
     * @return int整型
     */
    int maxPoints(vector<vector<int> >& points) {
        // write code here
        // 时间复杂度O(n³)
        int result = 0;
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i + 1; j < points.size(); ++j) {
                int cnt = 2;
                vector<int> v0 = {points[i][0] - points[j][0], points[i][1] - points[j][1]};
                for (int k = j+1; k < points.size(); ++k) {
                    vector<int> v1 = {points[i][0] - points[k][0], points[i][1] - points[k][1]};
                    if (v0[0] * v1[1] == v0[1] * v1[0]) {
                        // 两向量共线
                        cnt++;
                    }
                }
                result = max(result, cnt);
            }
        }
        return result;
    }
};

// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param points int整型vector<vector<>> 
//      * @return int整型
//      */
//     int maxPoints(vector<vector<int> >& points) {
//         // write code here
        
//         // double为斜率,后面存储坐标点
//         map<double,set<pair<double,double>>> m_1;
//         // 处理共竖线和共横线的情况；
//         map<string,set<pair<double,double>>> m_2;
        
//         // 第i个点
//         for(int i=0; i<points.size(); ++i)
//         {
//             double x_1 = (double)points[i][0];
//             double y_1 = (double)points[i][1];
//             // i之后的点
//             for(int j=i+1; j<points.size(); ++j)
//             {
//                 double x_2 = (double)points[j][0];
//                 double y_2 = (double)points[j][1];

//                 // 两点之间的坐标距
//                 double x_len = x_2-x_1;
//                 double y_len = y_2-y_1;

//                 // 共竖线
//                 if(x_len==0)
//                 {
//                     m_2["sameX"].emplace(make_pair(x_1,y_1));
//                     m_2["sameX"].emplace(make_pair(x_2,y_2));
//                 }
//                 // 共横线
//                 else if(y_len==0)
//                 {
//                     m_2["sameY"].emplace(make_pair(x_1,y_1));
//                     m_2["sameY"].emplace(make_pair(x_2,y_2));
//                 }
//                 // 其它斜率
//                 else
//                 {
//                     m_1[y_len/x_len].emplace(make_pair(x_1,y_1));
//                     m_1[y_len/x_len].emplace(make_pair(x_2,y_2));
//                 }
//             }
//         }

//         int ans = 0;

//         for(auto it=m_1.begin(); it!=m_1.end(); ++it)
//             ans = max(ans,(int)(it->second).size());

//         ans = max(ans,(int)m_2["sameX"].size());
//         ans = max(ans,(int)m_2["sameY"].size());

//         return ans;
//     }
// };