遇到一个平行线问题，求解答
为了管理动物园不听话的大猩猩们，动物管理员决定去远方的动物之城找一些平行线。当他逛到一个神奇的店铺时，他发现了一副黑色的图，上面依稀可见一些白色的点。动物管理员询问店铺老板这幅画是什么，老板说：“天机不可泄露”。动物管理员仔细端详了一会这幅画后，他发现其中的一些白点可以连成两条平行线。动物管理员问这幅画多少钱，老板说：“原价 ¥99999999999，但现在你只要计算出来这里面有几对平行线，就可以打折，有几对平行线就价值多少钱”。请你计算出动物管理员最少需要支付多少钱？输入一个整数n,表示总共有n个点（1<= n<= 1000）;和一个含有n组数据(xi, yi) 的数组，(xi,yi) 表示二维平面上一个点 (1<= xi,yi <= 1000)，且每个点均不重复。输出 n 个点能够找出几对平行线。（答案不超过 int）
写回答
-
任意两点确定一条直线。判断两条直线是否平行就是比较两条直线的斜率。这道题对于由不同的点确定的但是重合在一起的直线应该也判断为一组平行线。一共有n个点，就有n*(n-1)/2条直线。对于点i和j确定的直线斜率为(yi-yj)/(xi-xj).使用一个数组保存斜率，然后排序。排序过后相同斜率的直线就在连续的位置了。假设斜率为 k 的直线有 a 条，对应着有 a*(a-1)/2 组平行线（任意两条相互平行）。遍历一次排序后的数组就可以得到结果。使用简单的冒泡排序可能会超时，考虑更快的快速排序，归并排序或者直接使用java 的排序函数。时间空间复杂度与排序算法有关。 因此输入：6 [[0,0],[1,0],[1,1],[3,1],[3,3],[5,4]] 输出：10
2021-12-23 18:55:59赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
