Leetcode-2280: represents the minimum number of line segments of a line graph

subject

Topic linking

Here's a two-dimensional array of integers stockPrices , among stockPrices[i] = [dayi, pricei] Indicates that the stock is dayi The price of is pricei . Broken line diagram It is a graph composed of several points on a two-dimensional plane , The abscissa represents the date , The ordinate represents the price , A line chart is formed by connecting adjacent points . For example, the following figure is an example ：

Please return what you need to represent a line chart Minimum number of line segments .

Example 1：

 Input ：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
 Output ：3
 explain ：
 The figure above shows the corresponding input diagram , The abscissa represents the date , The ordinate represents the price .
 following  3  A line segment can represent a line graph ：
-  Line segment  1 （ Red ） from  (1,7)  To  (4,4) , after  (1,7) ,(2,6) ,(3,5)  and  (4,4) .
-  Line segment  2 （ Blue ） from  (4,4)  To  (5,4) .
-  Line segment  3 （ green ） from  (5,4)  To  (8,1) , after  (5,4) ,(6,3) ,(7,2)  and  (8,1) .
 Can prove that , Cannot use less than  3  A line segment represents this line chart .

Example 2：

 Input ：stockPrices = [[3,4],[1,2],[7,8],[2,3]]
 Output ：1
 explain ：
 As shown in the figure above , A line graph can be represented by a line segment .

Problem solving

Method 1 ： Judge that the slope is equal ( Convert to multiplication )

Divide by a[0]/b[0]==a[1]/b[1] Into Multiplication , Accuracy problems can be avoided , rounding . There are probably two different slopes , But it's rounded to equal .

This problem is actually to calculate the slope of this broken line
（ Note that conversion to multiplication will overflow , So use uint64_t）

class Solution {
    
public:
    bool compareVec(vector<int>& a,vector<int>& b){
    
        return (uint64_t)a[0]*b[1]==(uint64_t)a[1]*b[0];
    }
    int minimumLines(vector<vector<int>>& stockPrices) {
    
        int n=stockPrices.size();
        vector<int> pre;
        int count=0;
        sort(stockPrices.begin(),stockPrices.end(),[](vector<int>&a,vector<int>&b){
    
            return a[0]<b[0];
        });
        for(int i=1;i<n;i++){
    
            vector<int> vec={
    stockPrices[i][0]-stockPrices[i-1][0],stockPrices[i][1]-stockPrices[i-1][1]};
            if(i==1) count=1;
            else{
    
                if(compareVec(pre,vec)) continue;
                else count++;
            }
            pre=vec;
        }
        return count;
    }
};