UOJ Logo a1b3c7d9的博客

博客

询问是否有一种办法,统计直线下点的个数

2019-11-04 16:25:33 By a1b3c7d9

在坐标系上,给出n个点,n条直线,统计每条直线下的所有点的个数,$n\leq 10^6$,如果能够做到$O(n)$就更好了。

评论

foreverlasting
对每条直线做一次类欧是$O(nlogn)$,其他的我就不会了QAQ
cszmc2004
说清楚一点,点的坐标的值域是多少?
WrongAnswer
只会 $O(n\sqrt n\log n)$ 分块,然而过不了。。。
OldDriverTree
我记得是个经典问题,可以搜搜论文

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。