三角形计数的一些问题及思路





今年ACM竞赛大陆的几个网络赛中,出现了两个有关三角形计数的问题,一个是天津赛区,一个是福州赛区。
天津赛区在前,但个人认为福州赛区的那个题目更难一些。
福州赛区的题目大致是说给你n个点,先在有若干个询问,每个询问是问其中的三个点构成一个三角形的话,他们内部包含多少个点。要求n^2logn的预处理,常数时间回答,才能通过。题目传送门
天津赛区的题目大致是说给你n个点,问其中任取四个点可以构成凸四边形的取法有多少种。这个实际上可以反过来算,转化为任取四个点构成一个三角形内含一点的情况有多少种。也可以解释为任取三点把所有内含的点个数加起来有多少。题目传送门。要求n^2logn的算法。
这两个问题非常类似,他们都依赖于极角,并且都可以通过预处理计算出一些非常重要的量,这些量包括:遍历地固定任意一点,对其他点按照这个点为极点进行极角排序;对每一个排序后的点,极角比它大但小于它的极角加上180度的点有多少个。前者可以n^2logn之间算得,后者可以利用一个栈的形式,扫描计算,能在n^2的时间内完成。
福州大学的题目基本上利用这两个量就可以直接算出来结果了,天津大学的题目还要计算一个部分和,并且思路需要转化为任取一点,计算有多少个三角形包含它,有一定的复杂。
另外还可以考虑计算给定的n个点中任取三个点可以构成多少个空三角形。目前我只想到n^3的算法,还没有想到n^2logn的算法。

本文来自Dora Blog,题目为三角形计数的一些问题及思路,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987