算法笔试模拟题精解之“平行线”
算法笔试模拟题精解之“平行线”
贡献者 | 黄信旭
简介：任意两点确定一条直线。判断两条直线是否平行就是比较两条直线的斜
率。这道题对于由不同的点确定的但是重合在一起的直线应该也判断为一组平行线。
此题使用简单的冒泡排序可能会超时，可以考虑更快的快速排序，归并排序或者直接
使用 java 的排序函数。
题目描述
等级：容易
知识点：数学
查看题目：平行线
为了管理动物园不听话的大猩猩们，动物管理员决定去远方的动物之城找一些平
行线。
当他逛到一个神奇的店铺时，他发现了一副黑色的图，上面依稀可见一些白色
的点。
动物管理员询问店铺老板这幅画是什么，老板说：“天机不可泄露”。动物管理员
仔细端详了一会这幅画后，他发现其中的一些白点可以连成两条平行线。
动物管理员问这幅画多少钱，老板说：“原价 ¥99999999999，但现在你只要计
算出来这里面有几对平行线，就可以打折，有几对平行线就价值多少钱”。请你计算
出动物管理员最少需要支付多少钱？
输入一个整数 n, 表示总共有 n 个点（1 <= n <= 1000）; 和一个含有 n 组数据
(xi, yi) 的数组，(xi, yi) 表示二维平面上一个点 (1 <= xi,yi <= 1000)，且每个点均不
重复。
输出 n 个点能够找出几对平行线。（答案不超过 int）
示例 1
输入：
6
[[0,0],[1,0],[1,1],[3,1],[3,3],[5,4]]
输出：
10
解题思路 : 排序问题
任意两点确定一条直线。判断两条直线是否平行就是比较两条直线的斜率。这道
题对于由不同的点确定的但是重合在一起的直线应该也判断为一组平行线。
一共有 n 个点，就有 n*(n-1)/2 条直线。对于点 i 和 j 确定的直线斜率为 (yi-yj)/(xi-xj).
使用一个数组保存斜率，然后排序。
排序过后相同斜率的直线就在连续的位置了。
假设斜率为 k 的直线有 a 条，对应着有 a*(a-1)/2 组平行线（任意两条相互平行）。
遍历一次排序后的数组就可以得到结果。
使用简单的冒泡排序可能会超时，考虑更快的快速排序，归并排序或者直接使用
java 的排序函数。
时间空间复杂度与排序算法有关。
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”