首页 > 代码库 > HDU 5020 容器标记斜率
HDU 5020 容器标记斜率
题意:给你n个点,让你求出三点共线的最大情况, 点数为1000个
题解:很显然 ,点数1000,普通枚举O(n3),肯定过不了了。
方法为map记录每个点和其他点连线的斜率,如果斜率出现次数大于2 ,Num += C(N,2);
代码:
#include<stdio.h> #include<iostream> #include<map> using namespace std; map<double , int> mark; int flag; struct Node { int x, y; }cun[1005]; void slove(Node a, Node b) { if (a.x == b.x) {flag ++ ;return ;} double k =(1.0 * (a.y - b.y)) / (1.0 * (a.x - b.x)); mark[k] ++; return ; } int slov(int a) { int k = a * (a-1) / 2; return k; } int main() { int t, n; scanf("%d",&t); while(t--) { scanf("%d", &n); mark.clear(); for(int i = 0; i < n; i++) { scanf("%d%d", &cun[i].x, &cun[i].y); } __int64 num = 0; flag = 0; for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { slove (cun[i], cun[j]); } map<double, int>::iterator my_Itr; for(my_Itr=mark.begin();my_Itr!=mark.end();++my_Itr) { int k = my_Itr->second; if(k >= 2) num += slov(k); } if(flag >= 2) num += slov(flag); flag = 0; mark.clear(); } printf("%I64d\n", num); } }
HDU 5020 容器标记斜率
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。