问一道算法题算出这些直线一共有多少个交点
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条直线，用一种时间复杂度最低的方法算出这些直线一共有多少个交点。
: 这里的直线的含义我觉得应该为线段