某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在，用户给出了 $n$ 种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。

题解

像我这种菜鸡看了题目描述就开始往网络流和DP上去考虑。。结果发现好像网络流很难这样做，然后DP我死活设计不出状态，打开题解以后发现这题原来是十分巧妙的计算几何。。

首先，由于 $a + b + c = 1$ ，所以我们只需要知道其中两个值就可以，并不需要准确了解第三个值，体现在算法中就是只记录 $a, b$ 。这样我们就可以把一种材料或者合金抽象成一个平面上的点，每个点的坐标为 $(a, b)$ 。

对于两个点 $(x_1, y_1), (x_2, y_2)$ 所代表的原料，他们能够合成的合金一定在这两点之间的线段上，其坐标为 $(ax_1 + bx_2, ay_1 + by_2)$ ，其中 $a + b = 1$ 。

而对于三个点即以上代表的原料，他们能够合成的合金一定在这些点的凸包上。

记代表原料的点集为 $A$ ，代表合金的点集 $B$ ，问题实际上就是求出 $A$ 的一个子集，使得其中点的凸包能够完全覆盖 $B$ 中的所有点。

讲实话这个东西我不会求。。我不知道用传统的方法该怎么做，所以就学了人家巧妙的转化成最短路的方法。

首先，我们 $O(n ^ 2)$ 枚举 $A$ 中的两个点 $N, M$ ，对于，如果 $B$ 中所有点都在的同侧（左侧或右侧，按下文判断方法应该是右侧顺时针）或是在上，则连接一条 $N \rightarrow M$ 的边。

判断方法如下：对于枚举到的点 $N, M$ ，枚举 $B$ 中的点 $K$ ，若所有 $K$ 满足

则连接一条 $N \rightarrow M$ 的边，最后用 Floyd 求最小环即可。

注：程序中的 $K$ 为小写， $N, M$ 分别为 $i, j$ ，这里是为了表述美观而更改。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <algorithm>
const int MAX_N = 500;
const int MAX_M = 500;
const double EPS = 1e-7;
const int INF = 0x3f3f3f3f;
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    friend inline Point operator-(const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend inline double operator*(const Point &a, const Point &b) {
        return a.x * b.y - a.y * b.x;
    }
    friend inline double dot(const Point &a, const Point &b) {
        return a.x * b.x + a.y * b.y;
    }
} a[MAX_M + 1], b[MAX_N + 1];
int m, n, map[MAX_N + 1][MAX_N + 1], f[MAX_N + 1][MAX_N + 1];
inline int floyd() {
    int res = INF;
    memcpy(f, map, sizeof(f));
    for (int k = 1; k <= m; k++) {
        for (int i = 1; i <= m; i++) {
            if (f[i][k] < INF) {
                for (int j = 1; j <= m; j++) {
                    f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
    }
    for (int i = 1; i <= m; i++) res = std::min(res, f[i][i]);
    return res;
}
int main() {
    memset(map, 0x3f, sizeof(map));
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++) scanf("%lf%lf%*lf", &a[i].x, &a[i].y);
    for (int i = 1; i <= n; i++) scanf("%lf%lf%*lf", &b[i].x, &b[i].y);
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) { 
            int k;
            for (k = 1; k <= n; k++) {
                double det = (a[i] - b[k]) * (a[j] - b[k]);
                if (det > EPS) break;
                if (fabs(det) < EPS && dot(a[i] - b[k], a[j] - b[k]) > EPS) break;
            }
            if (k == n + 1) map[i][j] = 1;
        }
    }
    int ans = floyd();
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

「JSOI2007」合金 - 计算几何，Floyd

Contents

题解

代码