安保系统 - 题目

KOI国的机密设施可以在坐标平面上表示为一个左下角为 $(0, 0)$，右上角为 $(N + 1, N + 1)$，且各边平行于坐标轴的正方形。正方形的每一条边都代表机密设施的墙壁。

机密设施内有 $N$ 个激光传感器，编号从 $0$ 到 $N - 1$。我们计划设计一个安全系统，通过这些激光传感器来探测机密设施内的入侵者。

每个激光传感器都可以表示为坐标平面上的一个点。当启动激光传感器时，它会从其位置向四个方向之一发射激光：上方（$+y$ 轴方向）、右方（$+x$ 轴方向）、下方（$-y$ 轴方向）或左方（$-x$ 轴方向）。由于激光会一直传播直到到达墙壁，因此激光的路径可以表示为连接传感器位置与墙壁上某一点的线段。

激光发射的方向编号为 $1$ 到 $4$。$1$ 代表上方，$2$ 代表右方，$3$ 代表下方，$4$ 代表左方。下图依次展示了向 $1$、$2$、$3$、$4$ 号方向发射激光的传感器示例。黑色圆点表示激光传感器，红色线段表示激光。

第 $i$ ($0 \le i \le N - 1$) 号激光传感器位于 $(X[i], Y[i])$，启动时会向 $D[i]$ 号方向发射激光。不同的激光传感器位于不同的位置。$X[i]$ 和 $Y[i]$ 是 $1$ 到 $N$ 之间的整数。

你可以自由决定是否启动每个激光传感器。但是，如果不同激光传感器发射的激光相交，可能会导致识别错误，因此必须确保激光（包括端点）互不相交。下图展示了激光相交的示例，激光之间可能在一点相交，也可能在线段上相交。

第 $i$ ($0 \le i \le N - 1$) 号激光传感器的重要度为 $W[i]$。重要度是一个数值，表示启动该传感器对安全工作的贡献程度。整个安全系统的安全水平是所有已启动激光传感器的重要度之和。

请编写一个函数，计算在确保激光互不相交的前提下，可能达到的最大安全水平。

你需要实现以下函数：

int max_level(vector<int> X, vector<int> Y, vector<int> D, vector<int> W)

$X, Y, D, W$：长度为 $N$ 的整数数组。对于所有 $i$ ($0 \le i \le N - 1$)，第 $i$ 号激光传感器的坐标为 $(X[i], Y[i])$，启动时向 $D[i]$ 方向发射激光，重要度为 $W[i]$。
该函数应返回在确保激光互不相交的前提下，可能达到的最大安全水平。

提交的源代码中不得执行任何输入输出函数。

考虑 $N = 4, X = [1, 2, 3, 4], Y = [1, 2, 3, 4], D = [1, 1, 4, 4], W = [1, 1, 1, 1]$ 的情况。评测程序将调用如下函数：

max_level({1, 2, 3, 4}, {1, 2, 3, 4}, {1, 1, 4, 4}, {1, 1, 1, 1})

下图展示了机密设施、内部传感器以及传感器发射的激光。启动 $0$ 号和 $1$ 号传感器，或者启动 $2$ 号和 $3$ 号传感器，都能使激光互不相交，且安全水平为 $2$。不存在比这两种方法安全水平更高的方案。

因此，函数应返回 $2$。

Sample grader 的输入格式如下：

Sample grader 的输出格式如下：

请注意，Sample grader 可能与实际评测时使用的评测程序不同。

QOJ.ac