hdu 5020 求三点共线的组合数(容器记录斜率出现次数)
容器 记录 出现 HDU 组合 次数 斜率 三点
2023-09-11 14:14:00 时间
题意:
给你n个点,问你3点共线的组合数有多少,就是有多少种组合是满足3点共线的。
思路:
给你n个点,问你3点共线的组合数有多少,就是有多少种组合是满足3点共线的。
思路:
一开始抱着试1试的态度,暴力了一个O(n^3),结果一如既往的超时了,然后又在刚刚超时的代码上直接加了一个优化,就是如果当前斜率出现的次数小于2次,那么第三重for就不用在跑了,结果,呵呵,又超时了,然后又尝试了一个方法,就是枚举每一个点,求出所有点跟他组成的线段的斜率,记录每个斜率出现的次数,比如当前的斜率0.5出现了8次,那么就Ans + C(8,2) 一开始写的是C(8,3)忘记了当前的这个点必须在线段上,所以wa了一发,最后答案再除以3就行了,因为任意一组情况中的三个点都得到了一个答案,所以除以3.具体的细节看代码。
#include<stdio.h> #include<map.h> using namespace std; typedef struct { double x ,y; }NODE; NODE node[1100]; double mkxl[1100]; map<double ,__int64>mark; double xl(int a ,int b) { if(node[a].x == node[b].x) return 1000000000.0; return (node[a].y - node[b].y) / (node[a].x - node[b].x); } int main () { int t ,n ,i ,j ; __int64 Ans; scanf("%d" ,&t); while(t--) { scanf("%d" ,&n); for(i = 1 ;i <= n ;i ++) scanf("%lf %lf" ,&node[i].x ,&node[i].y); Ans = 0; for(i = 1 ;i <= n ;i ++) { mark.clear(); int nowid = 0; for(j = 1 ;j <= n ;j ++) { if(i == j) continue; if(++mark[xl(i ,j)] == 1) mkxl[++nowid] = xl(i ,j); } for(j = 1 ;j <= nowid ;j ++) { __int64 tmp = mark[mkxl[j]]; if(tmp >= 2) Ans += tmp * (tmp - 1) / 2; } } printf("%I64d\n" ,Ans / 3); } return 0; }
相关文章
- 7 -- Spring的基本用法 -- 4... 使用 Spring 容器:Spring 容器BeanFactory、ApplicationContext;ApplicationContext 的国际化支持;ApplicationContext 的事件机制;让Bean获取Spring容器;Spring容器中的Bean
- 获取一个容器的宽
- 盛最多水的容器
- Vue - 动态改变元素容器(非页面body)滚动条位置(设置指定子元素div的滚动条位置)
- 应用容器云:接过Java EE的枪
- 容器和虚拟化
- 小程序开发基础-view视图容器
- Docker容器------compose容器集群的快速编排
- ASP.NET Core应用程序容器化、持续集成与Kubernetes集群部署(一)
- Servlet 容器
- iOS H5容器的一些探究(二):iOS 下的黑魔法 NSURLProtocol
- STL之vector容器的实现框架
- 模型容器Containers之nn.ModuleDict