分数: 100 点
问题陈述
你被给予 N 不同的整数网格点 平面中的 (X_i, Y_i) \ (i = 1, 2, \dots, N) ,每一个都有一个整数分数 P_i。 您可以在以下条件下从其中选择任意数量的网格点。 求所选网格点得分总和的最大值。
条件: 一个网格点 占主导地位 由 凸组合 必须选择所选网格点的 。 也就是说,对于每个 k = 1, 2, \dots, N,如果存在元组 (\lambda_1, \lambda_2, \dots, \lambda_N) of N 非负 具有以下条件的实数,则 选择 (X_k, Y_k) : 选择
- \lambda_i > 0 \implies (X_i, Y_i) 。
- \sum_{i=1}^N \lambda_i = 1.
- \sum_{i=1}^N \lambda_i X_i \geq X_k.
- \sum_{i=1}^N \lambda_i Y_i \geq Y_k.
约束
- 1 \leq N \leq 200
- 1 \leq X_i \leq 10^9 \ \ (1 \leq i \leq N)
- 1 \leq Y_i \leq 10^9 \ \ (1 \leq i \leq N)
- (X_i, Y_i) \neq (X_j, Y_j) \ \ (i \neq j)
- |P_i| \leq 10^7 \ \ (1 \leq i \leq N)
输入
输入由标准输入按以下格式给出:
N X_1 \ Y_1 \ P_1 X_2 \ Y_2 \ P_2 \vdots X_N \ Y_N \ P_N
输出
打印在该条件下选择的网格点得分总和的最大值。
示例输入 1
3 1 4 2 4 1 3 2 2 -4
示例输出 1
3
最好只选择 (X_2, Y_2) = (4, 1)。 如果你选择 (X_1, Y_1) = (1, 4) 另外,那么例如 \lambda_1 = 0.4 和 \lambda_2 = 0.6 满足
\[ \lambda_1 + \lambda_2 = 0.4 + 0.6 = 1\\[1mm] \lambda_1 X_1 + \lambda_2 X_2 = 0.4 \times 1 + 0.6 \times 4 = 2.8 \geq 2 = X_3\\[1mm] \lambda_1 Y_1 + \lambda_2 Y_2 = 0.4 \times 4 + 0.6 \times 1 = 2.2 \geq 2 = Y_3, \]
因此 必须另外选择 (X_3, Y_3) = (2, 2) ,这会减少分数总和。
示例输入 2
3 1 4 2 4 1 3 2 2 -1
示例输出 2
4
选择所有网格点是最佳的。
示例输入 3
3 1 4 2 4 1 3 1 1 -6
示例输出 3
0
有时最好不选择网格点。