描述:
-
给定平面上的n个点,任意做一条直线,求至多能有几个点恰好落在直线上。
- 输入:
-
包含多组测试数据,每组测试数据由一个整数n(0<=n<=100)开始,代表平面上点的个数。
接下去n行每行给出一个点的坐标(x,y),x、y的绝对值均小于等于100。
- 输出:
-
对于每组测试数据,输出一个整数,表示至多能有几个点恰好落在直线上。
- 样例输入:
-
20 01 140 01 12 2 3 6
- 样例输出:
-
23
//分数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
mp ; //Node 为分数。 做分数->int的映射。 map ::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< <