博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
题目1548:平面上的点
阅读量:5761 次
发布时间:2019-06-18

本文共 1482 字,大约阅读时间需要 4 分钟。

描述:

给定平面上的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<
<

  

转载于:https://www.cnblogs.com/liyangtianmen/p/3573700.html

你可能感兴趣的文章
HDOJ-2069Coin Change(母函数加强)
查看>>
遍历Map的四种方法
查看>>
IOS atomic与nonatomic,assign,copy与retain的定义和区别
查看>>
JAVA学习:maven开发环境快速搭建
查看>>
Altium Designer 小记
查看>>
【Linux高级驱动】I2C驱动框架分析
查看>>
赵雅智:js知识点汇总
查看>>
二维有序数组查找数字
查看>>
JavaScript(ES5)使用保留字作函数名
查看>>
20个Linux服务器性能调优技巧
查看>>
多重影分身:一套代码如何生成多个小程序?
查看>>
Oracle将NetBeans交给了Apache基金会
查看>>
填坑记:Uncaught RangeError: Maximum call stack size exceeded
查看>>
SpringCloud之消息总线(Spring Cloud Bus)(八)
查看>>
DLA实现跨地域、跨实例的多AnalyticDB读写访问
查看>>
基于Hyperledger Fabric交易系统帐户的钱包模型的java Chaincode实例
查看>>
实时编辑
查看>>
北漂之毕业裁员后的又一波奇遇
查看>>
Python数据分析:pandas常用函数
查看>>
KVO原理分析及使用进阶
查看>>