首页 > 代码库 > HDU 1432 Lining Up（几何）
HDU 1432 Lining Up（几何）
http://acm.hdu.edu.cn/showproblem.php?pid=1432
题目大意：
2维平面上给定n个点，求一条直线能够穿过点数最多是多少。
解题思路：
因为题目给定的n（1~700），所以枚举，时间复杂度是O（n^3），不会超时。
枚举两个点，然后判断剩下的点是否在这条直线。
AC代码：
1 #include<cstdio> 2 3 struct Point{ 4 int x, y; 5 6 Point(int x = 0, int y = 0): x(x), y(y){} 7 8 void scan(){ 9 scanf("%d%d", &x, &y);10 }11 };12 13 typedef Point Vector;14 15 Vector operator - (Vector A, Vector B){//重载结构体减号16 return Vector(A.x - B.x, A.y - B.y);17 }18 19 int cross(Vector A, Vector B){//叉乘20 return A.x * B.y - A.y * B.x;21 }22 23 Point p[700];24 int n;25 26 int main(){27 while(~scanf("%d", &n)){28 for(int i = 0; i < n; ++i){29 p[i].scan();30 }31 32 int best = 0;//记录直线穿过最多的点个数33 for(int i = 0; i < n; ++i){34 for(int j = i + 1; j < n; ++j){35 int num = 2;//因为直线穿过i和j点，所以直线上已经有两个点了36 for(int k = j + 1; k < n; ++k){37 if(!cross(p[i] - p[j], p[i] - p[k])){//判断点k在直线ij上38 ++num;39 }40 }41 if(best < num){//更新最优值 42 best = num;43 }44 }45 }46 printf("%d\n", best);47 }48 return 0;49 }
HDU 1432 Lining Up（几何）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。