Description

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

 

Solution

需要特别注意的地方：

1.题意未提及所给定的point是否会重叠，因此若有多个点在同一位置的情况应当都计入结果。对于这一点，可以考虑遍历point并将位置相同的point合并得到一个权值，之后使用新的带有权值的点集进一步计算。

2.题目涉及斜率，竖直的直线需要另外处理，得到的解与一般情形取取最大。

题目要求计算最多有多少point处在一条直线上。对于这个问题，试图找出一组point组合然后验证是否在一条直线的办法显然是不可行的。换个角度，可以将问题转化为研究由两两点对组成的向量(p1->p2)，向量的权值是两端的point的权值之和，判断point共线就变成了判断向量共线。这样每次能得到一组共线向量，只要将向量的权值相加并去除重复计算的point的权值就可以得到一个解，遍历每组向量可求得最大解。

N个点可以得到N*(N-1)/2条向量，将这些线段以起始point为关键字排序。这样可以使以同一个point出发的向量在数组的相邻位置，并使用std::map维护以这个point出发的向量的每个斜率下的权值之和，各个斜率下的权值之和中的最大的那个就是以该point为起点的向量所能产生的最大解。因此，只要遍历每个point为起点的向量组即可得到解。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
struct Slope
{
    int dy,dx;//两点的y坐标差的绝对值，两点的x坐标差的绝对值（向量p1->p2）
    int sign;//符号位，斜率为负sign取-1，斜率为正sign取1
};
struct Line {//向量(p1->p2)
    Point p1,p2;//形成线段的两点
    Slope slp;//描述线段斜率的结构体
    int power;//线段的权值
    int begin_point_power;//p1的权值（去重复时使用）
    bool vis;//线段是否已访问
};
struct cmp_line
{
    bool operator()(const Line& l1, const Line& l2)
    {
        if(l1.p1.x == l2.p1.x)
        {
            return l1.p1.y < l2.p1.y;
        }
        return l1.p1.x < l2.p1.x;
    }
};
struct cmp_point
{
    bool operator()(const Point& p1, const Point& p2)
    {
        if(p1.x == p2.x) return p1.y < p2.y;
        return p1.x < p2.x;
    }
};
struct cmp_slope
{
    bool operator()(const Slope& p1, const Slope& p2)
    {
        if(p1.sign != p2.sign)
        {
            return p1.sign < p2.sign;
        }
        else
        {
            long long int left = p1.dy * p2.dx;
            long long int right = p2.dy * p1.dx;
            if(p1.sign == 1)
            {
                return left < right;
            }
            else
            {
                return right > left;
            }
        }
        return 0;
    }
};
class Solution {
public:
    int gcd(int x, int y)
    {
        if(y == 0) return x;
        return gcd(y, x % y);
    }
    Slope get_slope(int dy, int dx)
    {
        Slope slp;
        (dy < 0 && dx > 0) || (dy > 0 && dx < 0) ? slp.sign = -1 : slp.sign = 1;
        if(dy < 0) dy = -dy;
        if(dx < 0) dx = -dx;
        int g = gcd(dy, dx);
        dy /= g;
        dx /= g;
        slp.dy = dy;
        slp.dx = dx;
        return slp;
    }
    int maxPoints(vector<Point>& points)
    {
        int size = points.size();
        if(size == 1) return 1;
        //对重复的Point的处理，得到新的带有权值的点集
        map<Point, int, cmp_point> M1;
        map<Point, int, cmp_point>::iterator mit1;
        for(int i = 0; i < size; i++)
        {
            Point p = points[i];
            mit1 = M1.find(p);
            if(mit1 != M1.end())
            {
                int second = (*mit1).second;
                M1.erase(mit1);
                M1.insert(make_pair(p, second + 1));
            }
            else
            {
                M1.insert(make_pair(p, 1));
            }
        }
        vector<Point> lst;
        vector<Point>::iterator vit1;
        vector<int> cnt;
        printf("points:\n");
        for(mit1 = M1.begin(); mit1 != M1.end(); mit1++)
        {
            lst.push_back((*mit1).first);
            cnt.push_back((*mit1).second);
        }
        size = lst.size();
        //计算竖直的直线可能产生的最大解
        map<int, int> M2;
        map<int, int>::iterator mit2;
        for(int i = 0; i < size; i++)
        {
            mit2 = M2.find(lst[i].x);
            if(mit2 != M2.end())
            {
                int second = (*mit2).second;
                M2.erase(mit2);
                M2.insert(make_pair(lst[i].x, second + cnt[i]));
            }
            else
            {
                M2.insert(make_pair(lst[i].x, cnt[i]));
            }
        }
        int ans1 = 0;
        for(mit2 = M2.begin(); mit2 != M2.end(); mit2++)
        {
            //printf("%d\n",(*mit2).second);
            ans1 = max(ans1, (*mit2).second);
        }
        //计算倾斜的直线可能产生的最大解
        vector<Line> lines;
        for(int i = 0; i < size; i++)
        {
            for(int j = i + 1; j < size; j++)
            {
                Point p1 = lst[i], p2 = lst[j];
                if(p1.x == p2.x)
                {
                    continue;
                }
                Slope slp = get_slope(p2.y - p1.y, p2.x - p1.x);
                Line line = {p1, p2, slp, cnt[i] + cnt[j], cnt[i], false};
                lines.push_back(line);
            }
        }
        sort(lines.begin(), lines.end(), cmp_line());
        for(int i = 0; i < (int)lines.size();i++)
        {
            printf("(%d,%d) -> (%d,%d), slope = %d / %d sign = %d, power = %d\n",
                   lines[i].p1.x,lines[i].p1.y,
                   lines[i].p2.x,lines[i].p2.y,
                   lines[i].slp.dy,lines[i].slp.dx,lines[i].slp.sign,
                   lines[i].power);
        }
        int ans2 = 0;
        map<Slope, int, cmp_slope> M3;
        map<Slope, int, cmp_slope>::iterator mit3;
        if(lines.size() > 0)
        {
            Line line = lines[0];
            for(int i = 0; i < (int)lines.size(); i++)
            {
                if(lines[i].p1.x != line.p1.x || lines[i].p1.y != line.p1.y)
                {
                    for(mit3 = M3.begin(); mit3 != M3.end(); mit3++)
                    {
                        ans2 = max(ans2, (*mit3).second);
                    }
                    M3.clear();
                    M3.insert(make_pair(lines[i].slp, lines[i].power));
                    line = lines[i];
                }
                else
                {
                    Slope slp = lines[i].slp;
                    mit3 = M3.find(slp);
                    if(mit3 != M3.end())
                    {
                        int second = (*mit3).second;
                        M3.erase(mit3);
                        M3.insert(make_pair(slp, second + lines[i].power - lines[i].begin_point_power));
                    }
                    else
                    {
                        M3.insert(make_pair(slp, lines[i].power));
                    }
                }
            }
            for(mit3 = M3.begin(); mit3 != M3.end(); mit3++)
            {
                ans2 = max(ans2, (*mit3).second);
            }
        }
        printf("ans1 = %d ans2 = %d\n",ans1, ans2);
        return max(ans1, ans2);
    }
};