今天上午去了物理会考, 所以九点半才能离开考场. 自己觉得会考考的很好, 但是实际情况 可能连我自己也不清楚. 我们差不多十点半左右才到达实验, 然后人其实也很少. 我和 @Burst_Zero 在隔壁的机房里看了一眼题, 然后觉得很没有意思, 就打起了 Game01.

发觉第一题可能是模拟退火, 然后就没写. 其实原来是这样的: 我们都强力要求 @hshs595 同学在拿到题以后第一时间转发到 ezs 上面, 结果他今天没有发. 后来到了实验他才说题 在清橙上 (= =) . 但是后来也发现题没什么可做的.

最后当然是全场挂菜, 没有一个上 100 的 (被范神嘲讽了一番)

题目描述大概是这样的三道题:

两元求交

问题描述

给平面上 \(n\) 圆. 你要寻找一个过原点的圆, 使得它与最多的圆相交.

这 \(n\) 个圆之前两两无公共点. 并且, 原点在所有的这 \(n\) 个圆之外.

输入格式

第一行一个数 \(n\).

下面 \(n\) 行, 每行三个数 \(x, y, r\), 表示一个圆的圆心与半径.

输出格式

输出一个数, 表示最多与几个圆相交.

数据规模

对于 60% 的数据,\(n \leq 100\).

对于 100% 的数据,\(n \leq 1000\).

坐标都是绝对值不超过 \(1000\) 的整数.

样例输入

3
1 3 2
-4 2 2
2 0 1

样例输出

3

数凸包

问题描述

给 \(n\) 个平面上的点. 它的所有的子集的凸包中有多少个本质不同的?

两个凸包本质不同当且仅当平面上存在一个点在且只在其中一个凸包内.

输入格式

第一行一个数 \(n\), 表示点的个数.

下面 \(n\) 行, 每行三个数, 表示点的坐标.

输出格式

一个数, 表示本质不同的凸包的个数.

数据规模和约定

对于所有的数据,\(n \leq 100\)

所有的点的坐标都是 \(-1000\) 到 \(1000\) 之间的整数.

点与点之间可能重合.

答案不超过 \(2^{63}-1\).

样例输入

5
0 0
0 1
1 0
1 1
2 0

样例输出

28

样例说明

这些凸包中, 有一个是空集, 5 个是包含单个点的, 10 个是线段, 9 个是三角形, 3 个四边形.

计算体积

问题描述

CSG 是一个描述三维体积的方式. 在这种方式中, 一个物体可以由如下几种方式定义:

  1. 某种 “原子性” 的物体, 例如球或者长方体
  2. 某两个物体的并
  3. 某两个物体的交
  4. 某个物体 “减去” 另一个物体, 即, 某个物体不在另外一个物体中的部分

我们考虑一种简单的 CSG 系统. 它包含了这几种指令:

  1. makeBall x y z r 创建一个球心在 \((x, y, z)\), 半径为 \(r\) 的球.
  2. makeCuboid x1 x2 y1 y2 z1 z2 创建一个边与坐标轴平行的长方体, 它在 \(x\) 轴上 的范围是 \([x_1, x_2]\),\(y\) 轴上的范围是 \([y_1, y_2]\),\(z\) 轴上的范围是 \([z_1, z_2]\). 保证 \(x_1 \leq x_2, y_1 \leq y_2, z_1 \leq z_2\).
  3. makeUnion p1 p2 创建一个新的物体, 它是之前创建的第 \(p_1\) 个物体和第 \(p_2\) 个物体的并.
  4. makeIntersection p1 p2 创建一个新的物体, 它是之前创建的第 \(p_1\) 个物体和第 \(p_1\) 个物体的交.
  5. makeDifference p1 p2 创建一个新的物体, 它是之前创建的第 \(p_1\) 个物体减去第 \(p_2\) 个物体.

例如, 下面的这串指令:

makeCuboid 0 1 0 1 0 1
makeBall 0 0 0 0.5
makeBall 1 1 1 1
makeUnion 1 2
makeDifference 4 3

创建了一个在一角多了一块, 同时在另一角被 “啃” 了一口的立方体.

可以计算出它的体积是 \(1 - \frac{\pi}{48} \approx 0.934550\)

你的工作是, 给定一串指令, 计算每一步得到的物体的体积.

输入格式

第一行是一个数 \(n\), 表示指令的条数

后面 \(n\) 条指令, 格式如题目所述.

输出格式

输出 \(n\) 个数, 表示每个指令得到的物体的体积, 保留 3 位小数. 你的答案和标准答案之间的偏差不超过 \(0.005\) 即可.

数据规模和约定

对于所有数据, 满足 \(n \leq 50\)

所有物体中的所有点的坐标的绝对值都不超过 \(2\).

样例输入

5
makeCuboid 0 1 0 1 0 1
makeBall 0 0 0 0.5
makeBall 1 1 1 1
makeUnion 1 2
makeDifference 4 3

样例输出

1.000
0.524
4.189
1.458
0.935

第一道题我看了一眼, 以为是模拟退火, 就没怎么去写 (再加上没时间). 其实正解是这样子的: 暴力枚举两个点, 计算如果需要中间的那个圆与这两个相交, 其弧度应该在哪个区间 内. 然后判断就可以了.

但是徐明宽大神说直接上辛普森积分也可以, 直接反演.

第二道题本质上就是求有多少个凸多边形, 所以我也不细说了.

第三道题看起来比较简单 (雾), 有这么几种做法:

  1. 骗分, 要求并就把两个体积加在一起, 求差就是体积相减, 这个做法可以骗到 10 分.
  2. 用撒点的方法, 再一个图形内大量产生随机点, 然后统计随机点的数量, 并用随机点来求交求差等等. 这个取决于实现, 通常可以拿到 30 分.
  3. 将物体拟合成多面体, 并用三角形来表示. 这种做法可能实现的复杂度很高, 但是 球体拟合成的多面体大概只需要一百到一千个面即可达到精度. 如果实现的好, 并且 使用了数据结构来维护三角形, 可能能拿到 100 分.
  4. 这个在精度上有问题, 需要用正方体来拟合球体. 我们会发现其实需要约数十万正方体 才能拟合一个球体, 并且精度会随即降低. 用八分三位线段树能够维护该结构, 但是 由于精度问题只能达到 10 分左右.
  5. 结合第一种撒点的方法和第四种八分树, 可以拿到满分, 即正解.

所以说计算几何通常被用来卡满分, 而且总是范神出题......

求大神帮续实力啊...... orz