UOJ Logo Universal Online Judge

UOJ

#352. 新年的五维几何

统计

在你的帮助下,SingleDog们终于进入了计算中心内部,他们惊讶的发现,计算中心的核心——AlphaGo的三台主机所在的地方,居然是一个多维空间!

简单点说,核心是 $n \leq 5$ 维空间里一个点集,位于一个 $n$ 维长方体的方框内部。方框内部由所有满足 $l_i\le x_i \le r_i$ 的点 $(x_1,x_2,\cdots,x_n)$ 构成,而核心则由所有位于方框内部且满足 $x_i - x_j \ge a_{i,j}$ 的点$(x_1, x_2 \cdots,x_n)$ 构成,其中 $l_i,r_i,a_{i,j}$ 均为给定的整数。

现在SingleDog们想知道的就是这个核心的“体积”占方框的体积的比例。

为了方便理解题意,一个等价的题目描述是:

设 $x_1,x_2,\cdots,x_n$ 是 $n$ 个实数变量,其中第 $i$ 个变量 $x_i$ 在区间 $[l_i,r_i]$ 内均匀随机生成,所有 $l_i$ 和 $r_i$ 均为给定的整数且 $l_i\le r_i$(约定 $l_i=r_i$ 时,$[l_i,r_i]$ 表示单元素集合 $\{l_i\}$)。

给定 $n\times n$ 的整数矩阵,矩阵的每个元素代表一个约束,其中第 $i$ 行第 $j$ 列的元素 $a_{i,j}$ 代表约束 $$x_i-x_j\ge a_{i,j}$$

求这 $n\times n$ 个约束同时被满足的概率。

输入格式

第一行包含一个正整数 $n$,表示实数变量个数。

接下来 $n$ 行,第 $i$ 行两个整数 $l_i,r_i$,描述第 $i$ 个区间。

接下来 $n$ 行,每行 $n$ 个整数,给出整数矩阵 $a_{i,j}$。

输出格式

输出一行,包含一个实数,表示所求的概率。

你的答案与参考答案的绝对误差不超过 $10^{-7}$ 时被认为是正确的。

样例一

input

1
0 10
-10

output

1.000000000000

explanation

无论变量 $x_1$ 的值是多少,约束 $x_1-x_1\ge-10$ 恒成立,故满足约束的概率为 $1$。

样例二

input

2
5 5
3 7
0 1
-3 0

output

0.2500000000

explanation

$x_1=5$,$3\le x_2\le 7$。仅当 $3\le x_2\le 4$ 时才能同时满足所有约束,故满足所有约束的概率为 ${1\over 4}=0.25$。

样例三

input

2
4 5
3 6
-10 2
-10 -10

output

0.0000000000

explanation

满足 $4\le x_1\le 5$,$3\le x_2\le 6$ 的 $x_1,x_2$ 有无穷多个,但只有一组值 $x_1=5,x_2=3$ 是满足约束的,故满足约束的概率为 $0$。

样例四

input

2
3 10
0 8
-1 1
-7 0

output

0.5982142857

explanation

满足约束的概率为 ${67\over 112}$。你输出的答案应当在 $[{67\over 112}-10^{-7},{67\over 112}+10^{-7}]$ 范围内。

样例五

input

3
0 10
2 10
2 9
0 -9 -10
4 0 -3
1 -4 0

output

0.1491071429

样例六

input

4
0 5
0 9
4 10
0 5
0 -8 -9 -5
1 0 -4 3
1 -6 0 3
-4 -10 -10 0

output

0.2622839506

样例七

input

5
0 10
0 10
4 4
0 9
0 7
-10 -9 -10 -10 -10
-10 -10 2 -10 -10
-10 -10 -10 1 -10
-10 -10 -10 -10 -5
-10 -10 -10 -10 -10

output

0.1191269841

样例八

input

5
0 2
1 8
7 10
2 7
6 10
0 -10 -10 -9 -10
-10 0 -7 -4 -8
3 3 0 1 -6
3 -6 -5 0 -5
-2 3 -9 1 0

output

0.1713095238

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 8 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 $n$ 其它限制
1 5 $=1$
2 10 $=2$ $l_1=r_1$
3 20 若 $j\ne i+1$,则 $a_{i,j}=-10$
4 15
5 10 $=3$
6 10 $=4$
7 20 $=5$ 若 $j\ne i+1$,则 $a_{i,j}=-10$
8 10

对于所有数据,$1\le n\le 5$,$0\le l_i\le r_i\le 10$,$-10\le a_{i,j}\le 10$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载