来源和评测点
2013 Multi-University Training Contest 1
Hdu4609
Caioj1454
题目
「题目大意」
有T组数据
每组数据给出n条线段,问任意取三条,可以组成三角形的概率
「输入格式」
开头一行输入T(T<=100)
下来T组数据,每组数据第一行输入一个n(3<=n<=10^5)
第二行输入n个数,表示n条线段
线段长度(1<=n<=10^5)
「输出格式」
每组数据输出一个数p
表示可以组成三角形的概率
保留七位小数
「输入样例」
2
4
1 3 3 4
4
2 3 3 4
「输出样例」
0.5000000
1.0000000
分析
其他快速傅里叶变换题目参见:Tag-快速傅里叶变换
大致思路:
计算出两条边的和,枚举第三边表示能和它搭配的数量,经过去重后,除以总组合数就是概率
两边之和:FFT,参考另外几道简单点的题
去重1:两边之和不能是来自同一条边
去重2:两边有一条比第三边大,另一个小
去重3:两边都比第三边大
去重4:两边有任何一条=第三边
(去重2、3、4后剩下的就是两边都比第三边小的情况)
输入的是q[i],$A(q[i])=是q[i]的数量$
NUM(i)表示两边之和=i的情况个数,用去重1
$$
NUM(i)=\frac{ A^2(i)-B(i) }{2}
$$
去重2、3、4利用排序,并用前缀和SUM获得区间和
$ ANS(i)=SUM(rn-1)-SUM(q[i]) $
$ 去重2:ANS(i)-=i\times (n-i-1) $
$ 去重3:ANS(i)-=\frac{ (n-i-2)\times (n-i-1) }{2} $
$ 去重4:ANS(i)-=n-1 $
$$
tot=\frac{ n\times (n-1)\times (n-2) }{2}
$$
答案就是
$$
\frac{ \sum_{i=0}^{n-1} ANS(i) }{tot}
$$
代码
1 |
|