描述：
给定平面上的n个点，任意做一条直线，求至多能有几个点恰好落在直线上。
包含多组测试数据，每组测试数据由一个整数n(0<=n<=100)开始，代表平面上点的个数。
接下去n行每行给出一个点的坐标(x,y)，x、y的绝对值均小于等于100。
对于每组测试数据，输出一个整数，表示至多能有几个点恰好落在直线上。
2 0 0 1 1 4 0 0 1 1 2 2 3 6
2 3
|
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 |
//分数struct
Node{ double
zi ; double
mu ; Node(){} ; Node(double
z , double
m):zi(z),mu(m){} ; friend
bool operator < (const
Node A , const
Node B){ return
A.zi * B.mu < A.mu * B.zi ; } friend
bool operator == (const
Node A , const
Node B){ return
A.zi * B.mu == A.mu * B.zi ; }};struct
Point { double
x ; double
y ;}p[108];int
n ;//固定一个点i必须出现，那么斜率相同的点就在一条直线上了，统计最大值 。int
get_max(int
id){ int
i ; double
x = p[id].x ; double
y = p[id].y ; int
ans = 0 ; map<Node , int> mp ; //Node 为分数。 做分数->int的映射。 map<Node , int> ::iterator it ; mp.clear() ; for(i = 1 ; i <= n ; i++){ if(i == id) continue
; if(p[i].x == x) ans++ ; else mp[Node(p[i].y - y , p[i].x - x)]++ ; } for(it = mp.begin() ; it != mp.end() ; it++) ans = max(ans , it->second) ; return
ans + 1 ;}int
main(){ int
i , ans ; while(cin>>n){ for(i = 1 ; i <= n ; i++) cin>>p[i].x>>p[i].y ; ans = 0 ; for(i = 1 ; i <= n ; i++) ans = max(ans , get_max(i)) ; cout<<ans<<endl ; } return
0 ;} |
原文：http://www.cnblogs.com/liyangtianmen/p/3573700.html