Skip to content

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 image-20210714222730898

样例输出 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了,可以的话,请您参考添加页面,与大家一起分享你的题解!