题意:平面内给定n个点q次询问,给次给定一个点P问这个点与平面内n个点可以组成多少直角三角形,其中(n+q)个点互不相等
分别考虑P点作直角顶点和非直角顶点这个題思路很简单,就是看如何实现简单而且不会tle!!!
对于直角顶点和非直角顶点代码都比较简单求后者有点离线的思想。
这里想说的就昰map的用法自定义小于运算符,使得在map中查找的时候统一斜率的向量都会加起来,虽然在map中依然会保存多个不同的向量(听说是现场┅血的写法,中山大学大佬nb)
算法复杂度大概n*n*log(n)(由于n和p的范围一样这里统一同n表示),运行时间10s左右
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。