1259: 高维距离

题目描述

在一维线段上，点 $(x_1)$ 距离原点的距离为 $\sqrt{x_1 ^ 2}$

在二维平面上，点 $(x_1, x_2)$ 距离原点的距离为 $\sqrt{x_1 ^ 2 + x_2 ^ 2}$

在三维空间里，点 $(x_1, x_2, x_3)$ 距离原点的距离为 $\sqrt{x_1 ^ 2 + x_2 ^ 2 + x_3 ^ 2}$

……

在 $n$ 维空间中，一个高速粒子被我们的摄像机捕获，并在镜头上留下了一道又长又模糊的影子。根据这个影子，我们可以大致确定这一个粒子的坐标 $(x_1, x_2, \dots, x_n)$。对于第 $i$ 维的坐标，$x_i$ 是一个落在区间 $[a_i, b_i]$ 中的一个整数。你需要求出，这个粒子到原点的距离有多少种不同的可能取值。

输入格式

第一行一个正整数 $n$ 表示空间的维度

接下来的 $n$ 行，每行两个用空格隔开的整数，第 $i$ 行表示 $a_i, b_i$

输出格式

输出一个整数，表示该粒子距离原点的可能取值数量

样例输入

样例输入 1

text 2 1 3 1 3

样例输入 2

text 5 1 2 2 3 3 4 4 5 5 6

样例输出

样例输出 1

text 6

样例输出 2

text 26

数据范围

时间限制：1000 ms 空间限制：256 mb

没有捆绑测试

全局限制

$1 \leq n \leq 100$
$-100 \leq a_i \leq b_i \leq 100$

部分显示

$(\text{30 points})~n \leq 3$
$(\text{30 points})~0 \leq a_i \leq b_i \leq 1$
$(\text{40 points})$ 无限制

你可能需要用到 bitset

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！