问一道算法题算出这些直线一共有多少个交点

http://www.newsmth.net/bbstcon.php?board=Algorithm&gid=8898

发信人: snoowball (Snowball), 信区: Algorithm
标  题: Re: 问一道算法题
发信站: 水木社区 (Fri Oct 26 09:30:33 2007), 站内

用Sweep line算法,时间复杂度是O((n+k)*logn),空间复杂度是O(n)
其中k是交点个数,适用于交点不太稠密
【 在 cutepig (cutepig) 的大作中提到: 】
: 一张白纸上画了N条直线,用一种时间复杂度最低的方法算出这些直线一共有多少个交点。
: 这里的直线的含义我觉得应该为线段

Powered by Jekyll and Theme by solid

本站总访问量