//
// Created by 高森森 on 2022/2/7.
//

#ifndef LEETCODE_SOLUTION23_H
#define LEETCODE_SOLUTION23_H

#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>
#include<float.h>
#include <algorithm>

using namespace std;

class Solution23 {
public:
    vector<int> bestLine(vector<vector<int>>& points) {
        int maxCnt=2;
        vector<int>res{0,1};
        for(int i=0;i<points.size();i++)
        {
            //注意这个map是每个i节点开始重新创建，因为为了计数重复
            unordered_map<double,pair<int,vector<int>>>hashmap;
            int x1=points[i][0];
            int y1=points[i][1];
            for(int j=i+1;j<points.size();j++){
                int x2=points[j][0];
                int y2=points[j][1];
                double k=(x1==x2)?DBL_MAX:(double)(y1-y2)/(double)(x1-x2);
                if(!hashmap.count(k)){
                   hashmap[k]=make_pair(2,vector<int>{i,j});
                }else{
                    hashmap[k].first++;
                }
                if(hashmap[k].first>maxCnt){
                    maxCnt=hashmap[k].first;
                    res=hashmap[k].second;
                }
            }
        }
        return res;
    }
};


#endif //LEETCODE_SOLUTION23_H