唐山网站公司建设网站,wordpress 构建知识库,想找工作去哪个网站,源代码 培训 网站CF603D Ruminations on Ruminants
给定n条直线#xff0c;两两不平行#xff0c;且任意三条直线不经过同一个点#xff0c;然后求解满足原点在外接圆上的由三条直线围成的三角形有多少个。
首先这道题只需要知道Simson theorem就可以做了。 定理内容是三角形外接圆上的点到…CF603D Ruminations on Ruminants
给定n条直线两两不平行且任意三条直线不经过同一个点然后求解满足原点在外接圆上的由三条直线围成的三角形有多少个。
首先这道题只需要知道Simson theorem就可以做了。 定理内容是三角形外接圆上的点到三角形三边的射影共线。 逆定理是满足到三角形三边射影共线的点在三角形外接圆上。
那么我们只需要求解出原点到每条直线的垂足然后枚举一个点计算出这个点到后面所有点的斜率然后相同斜率的就可以产生贡献相当于统计平面内三点共线的对数我们可以通过枚举排序做到O(n2)O(n^2)O(n2)
这里有个技巧就是斜率不存在的点我们将它们的斜率设为INF。
另外还需要特判一下垂足重合的情况只会出现在直线经过原点的情况其他时候垂足一定直线就是一定的。
