首页 > 代码库 > HDU5020(判断三点共线)BestCoder Round #10(1003)
HDU5020(判断三点共线)BestCoder Round #10(1003)
Revenge of Collinearity
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 184 Accepted Submission(s): 51
Problem Description
In geometry, collinearity is a property of a set of points, specifically, the property of lying on a single line. A set of points with this property is said to be collinear (often misspelled as colinear).
---Wikipedia
Today, Collinearity takes revenge on you. Given a set of N points in two-dimensional coordinate system, you have to find how many set of <Pi, Pj, Pk> from these N points are collinear. Note that <Pi, Pj, Pk> cannot contains same point, and <Pi, Pj, Pk> and <Pi, Pk, Pj> are considered as the same set, i.e. the order in the set doesn’t matter.
---Wikipedia
Today, Collinearity takes revenge on you. Given a set of N points in two-dimensional coordinate system, you have to find how many set of <Pi, Pj, Pk> from these N points are collinear. Note that <Pi, Pj, Pk> cannot contains same point, and <Pi, Pj, Pk> and <Pi, Pk, Pj> are considered as the same set, i.e. the order in the set doesn’t matter.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with an integer N, following N lines, each line contains two integers Xi and Yi, describing a point.
[Technical Specification]
1. 1 <= T <= 33
2. 3 <= N <= 1 000
3. -1 000 000 000 <= Xi, Yi <= 1 000 000 000, and no two points are identical.
4. The ratio of test cases with N > 100 is less than 25%.
Each test case begins with an integer N, following N lines, each line contains two integers Xi and Yi, describing a point.
[Technical Specification]
1. 1 <= T <= 33
2. 3 <= N <= 1 000
3. -1 000 000 000 <= Xi, Yi <= 1 000 000 000, and no two points are identical.
4. The ratio of test cases with N > 100 is less than 25%.
Output
For each query, output the number of three points set which are collinear.
Sample Input
2 3 1 1 2 2 3 3 4 0 0 1 0 0 1 1 1
Sample Output
1 0
题意:给出n个点,找出三点贡献的点的集合
思路:n=1000,我比赛的时候实在没思路,虽然知道暴力n^3一定会超时,但还也写完意思的交了一发,平时几乎不碰几何党的飘过~
赛后看了某神犇的代码,思路瞬间开阔了
就是将n个点按x,y从小到大排序,x为第一关键字,y为第二关键字
排完序以后就是两层for暴搜了,因为已经排好序,就可以按斜率将所有斜率一样的点归为一个集合
假设当前要判断的点为i,有p个点与之共线,因为i是一定要选的,所以只需在剩下的p个点中选择2个就好了,为p*(p-1)/2
累加这些就是答案了
<script src="https://code.csdn.net/snippets/471923.js" type="text/javascript"></script>
HDU5020(判断三点共线)BestCoder Round #10(1003)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。