JSOI 2007 合金

发表于2020-07-18更新于2023-09-15字数统计1k阅读时长9分

合金

Description

有 m 种原材料由铁、铝、锡组成的合金，不同合金有不同铁铝锡的比重 aia_i, bib_i, cic_i。将每种原材料取出一定量，经过融解、混合，得到新的合金。现需要 nn 种合金，铁铝锡的比重为 did_i, eie_i, fif_i。求最少需要的原材料种数。

Solution

设有合金 (a1,b1,c1)(a_1, b_1, c_1) 与 (a2,b2,c2)(a_2, b_2, c_2)，欲合成合金 (d,e,f)(d, e, f)。
则有

{k1(a1,b1,c1)+k2(a2,b2,c2)=(d,e,f)k1(1−b1−a1)+k2(1−b2−a2)=1−d−e\left\{ \begin{array}{lr} k_1 (a_1, b_1, c_1)+k_2 (a_2, b_2, c_2)=(d, e, f)\\ k_1 (1-b_1-a_1)+k_2 (1-b_2-a_2)=1-d-e\\ \end{array} \right.

如果只考虑2维，那么有

{k1(a1,b1)+k2(a2,b2)=(d,e)k1+k2+k1(−b1−a1)+k2(−b2−a2)=1−d−e\left\{ \begin{array}{lr} k_1 (a_1, b_1)+k_2 (a_2, b_2)=(d, e)\\ k_1+k_2+k_1 (-b_1-a_1)+k_2 (-b_2-a_2)=1-d-e\\ \end{array} \right.

可得

{k1(a1,b1)+k2(a2,b2)=(d,e)k1+k2=1\left\{ \begin{array}{lr} k_1 (a_1, b_1)+k_2 (a_2, b_2)=(d, e)\\ k1 + k2 = 1\\ \end{array} \right.

即

  • 若 2 种合金 (a1,b1,c1)(a_1, b_1, c_1)，(a2,b2,c2)(a_2, b_2, c_2) 能合成合金 (d,e,f)(d, e, f)，则 (a1,b1)(a_1, b_1)、(a2,b2)(a_2, b_2)、(d,e)(d, e) 三点共线，且点 (d,e)(d, e) 位于两点之间。
  • 若有 3 种合金，对应三个点，则先连接其中两点，两点所连线段上的点都可以被表示；再将线段上的点与第三个点连接，所连的线段上的点均可被选取。即三点所围的点都能被表示出来。

于是问题转化为求原材料合金对应二维坐标的凸包(点最少)，该凸包能否将所需要的材料对应二维坐标的凸包给围住。
对于两个坐标，如果所需要的材料对应的坐标均在所连向量的左侧(通过向量外积判断)，则两点连边单向边，长度为 1。通过弗洛伊德最小环可得到最少的原料数。

注意：

  • 若所需材料的坐标在原材料坐标所连直线上(此时向量外积为0)，则需通过向量内积判断是否在原材料坐标所连线段上
  • 注意比较时的精度 epsilonepsilon

Code

合金
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 505;
constexpr double EPSILON = 1e-15;

struct Vector {
    Vector() = default;
    Vector(double _x, double _y) : x(_x), y(_y) {}

    friend inline double operator* /*×*/(const Vector& a, const Vector& b) {
        return a.x * b.y - a.y * b.x; //向量外积
    }

    friend inline Vector operator-(const Vector& a, const Vector& b) {
        return Vector(a.x - b.x, a.y - b.y);
    }

    friend inline double dotProduct(const Vector& a, const Vector& b) {
        return a.x * b.x + a.y * b.y; //向量内积
    }

    double x = .0, y = .0;
} mat[MAXN], pro[MAXN];  // material and product

int n, m, ans(0x3f3f3f3f), dis[MAXN][MAXN];

inline void init() {
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++) {
            bool connect = true;
            for (int k = 1; k <= n; k++) {//判断是否能作为凸包的边
                double cross = (mat[j] - mat[i]) * (pro[k] - mat[i]);
                double dot = dotProduct(mat[j] - pro[k], mat[i] - pro[k]);
                if (cross < -EPSILON || (abs(cross) < EPSILON && dot > EPSILON))
                    connect = false;
            }
            if (connect) dis[i][j] = 1;
        }
}

inline void floyed() { //floyed求最小环
    for (int k = 1; k <= m; k++)
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
    for (int i = 1; i <= m; i++) ans = min(ans, dis[i][i]);
    cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> m >> n;

    double a, b, c;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        mat[i] = Vector(a, b);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a >> b >> c;
        pro[i] = Vector(a, b);
    }
    init();
    floyed();
    return 0;
}