Description

共 $T$ 组数据。在一个三维坐标系上，有 $n$ 个球体，坐标分别为 $(x_i, y_i, z_i)$，半径为 $r$ 。现在从 $z$ 轴的 $0$ 位置出发，所经过的位置一定要有球体覆盖，求能否到达 $z$ 轴的 $h$ 位置。

$(1 \leq n \leq 10^3,1 \leq h,r \leq 10^9,T \leq 20$，坐标的绝对值不超过 $10^9)$

Description

给定 $n$ 个点，每个点的坐标为 $(x_i,y_i)$，且点 $(x,y)$ 到它周围 $8$ 个点

$(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)$

的距离均为 $1$ 。现要找到一个点，使其它点到这个点的距离和最小，输出这个最小值。

$(0 \leq n \leq 10^5,-10^9 \leq x_i,y_i \leq 10^9)$

Description

给定 $n$ 个点，每个点的坐标为 $(x_i,y_i)$，且点 $(x,y)$ 到它周围 $8$ 个点

$(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)$

的距离均为 $1$ 。现要找到一个点，使其它点到这个点的距离和最小，输出这个最小值。

$(0 \leq n \leq 10^5,-10^9 \leq x_i,y_i \leq 10^9)$

Description

构造一个无向图（没有自环），使这个无向图恰好有 $m$ 个三元环，输出这个无向图的 $01$ 矩阵。

$($无向图的顶点数不超过 $100,1 \leq m \leq 10^5)$

Description

当 $x \geq 4$ 时，$f_x = c^{2x - 6} \cdot f_{x - 1} \cdot f_{x - 2} \cdot f_{x - 3}$ 。

现在已知 $n,f_1,f_2,f_3,c$ 的值，求 $f_n$ 的值，对 $10^9 + 7$ 取模。

$(4 \leq n \leq 10^{18},1 \leq f_1,f_2,f_3,c \leq 10^9)$

Description

信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 $\frac{1}{4}$ 圆。现在平面上有 $n$ 张竖直方向长为 $a$，水平方向长为 $b$，圆半径为 $r$ 的信用卡，给定每张信用卡的坐标 $(x,y)$ 和旋转的弧度 $\theta$，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。

$(1 \leq n \leq 10^4,0.1 \leq a,b \leq 10^6,0.0 \leq r < \min \{ \frac{a}{4},\frac{b}{4} \};|x|,|y| \leq 10^6, 0 \leq \theta < 2\pi)$

Description

信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 $\frac{1}{4}$ 圆。现在平面上有 $n$ 张竖直方向长为 $a$，水平方向长为 $b$，圆半径为 $r$ 的信用卡，给定每张信用卡的坐标 $(x,y)$ 和旋转的弧度 $\theta$，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。

$(1 \leq n \leq 10^4,0.1 \leq a,b \leq 10^6,0.0 \leq r < \min \{ \frac{a}{4},\frac{b}{4} \};|x|,|y| \leq 10^6, 0 \leq \theta < 2\pi)$

Description

给定 $n$ 个点，求出最短的包围所有点的轮廓且满足任意点到轮廓的距离不小于给定的 $L$ 。

$(3 \leq n \leq 10^3,1 \leq L \leq 10^3,-10^4 \leq x_i,y_i \leq 10^4)$

Description

给定一个长度为 $n$ 的线性地图 $\{s\}$，# 表示障碍，. 表示可以停留。小 $\rm X$ 和小 $\rm Y$ 分别站在 $a$ 处和 $b$ 处，现在小 $\rm X$ 想去 $c$，小 $\rm Y$ 想去 $d$ 。一个人一次只能走一格或两格，不能站在障碍和另一个人所在的位置，也不能反向走。求能否使小 $\rm X$ 和小 $\rm Y$ 都到达目的地。

$(4 \leq n \leq 2 \times 10^5,1 \leq a,b,c,d \leq n;a,b,c,d$ 互不相同，且 $a < b < d,a < c;s_a,s_b,s_c,s_d$ 均不为 # $)$

Description

给定 $n$ 头牛和 $b$ 座牛棚，已知每头牛最喜欢，第 $2$ 喜欢，第 $3$ 喜欢，……，第 $b$ 喜欢的牛棚分别是什么，以及每个牛棚的容量 $v_i$（最多能住 $v_i$ 头牛）。如果某头牛住在第 $i$ 喜欢的牛棚里，则这头牛的不满意度为 $i$ 。求如何分配牛棚，使所有牛的 最大不满意度 - 最小不满意度 + 1 的值最小。输出这个值是多少。

$(1 \leq n \leq 10^3,1 \leq b \leq 20,\sum\limits_{i = 1}^n v_i = n)$