[JSOI 2007] 合金

发表于2017-05-08更新于2020-08-06

题目大意

有一种铁、铝、锡的合金，给定 mm 种原料合金三元素的百分比，以及 nn 种需求合金三元素的百分比，求要能制作出所有的需求合金所需原料合金的最少种数。

1⩽n,  m⩽5001 \leqslant n, \; m \leqslant 500

题目链接

【JSOI 2007】合金 - Luogu 4049

题解

由于三元素百分比之和一定是 11 ，所以一种原料或需求可以转化为平面上的点（好神啊）。

发现两种原料能合成对应两点线段上的所有点，多点能合成其围成的多边形内的所有点。

所以问题转化为，有两个点集，从一个点集中选出最少的点围住另一个点集内的所有点。

枚举原料点集内的两点 ii 、jj ，若需求点集内的所有点都在其向量左前方，则令 dist(i,j)=1dist(i, j) = 1 ，否则为无穷，最后用 floyd 求一个最小环，min{dist(i,i)}min\{dist(i, i)\} 就是答案。

注意特判所有点都重合的情况。

代码

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
#include <cstdio>
#include <climits>
#include <cmath>
#include <algorithm>
const int MAXN = 505;
const double EPS = 1e-10;
int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    if (x > EPS) return 1;
    return -1;
}
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    friend Point operator-(const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend double cross(const Point &a, const Point &b) {
        return a.x * b.y - a.y * b.x;
    }
    friend double dot(const Point &a, const Point &b) {
        return a.x * b.x + a.y * b.y;
    }
} a[MAXN], b[MAXN];
int m, n;
int dist[MAXN][MAXN];
void calcDist() {
    for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) dist[i][j] = INT_MAX;
    for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) if (i != j) {
        bool flag = true;
        for (int k = 1; k <= n; k++) {
            int t = dcmp(cross(a[j] - a[i], b[k] - a[i]));
            if (t < 0 || (t == 0 && dcmp(dot(a[j] - a[i], b[k] - a[i])) < 0)) {
                flag = false;
                break;
            }
        }
        if (flag) dist[i][j] = 1;
    }
}
void floyd() {
    for (int k = 1; k <= m; k++) for (int i = 1; i <= m; i++) if (dist[i][k] < INT_MAX) {
        for (int j = 1; j <= m; j++) if (dist[k][j] < INT_MAX)
            dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
    }
}
bool isSame() {
    for (int i = 2; i <= m; i++)
        if (dcmp(a[i].x - a[1].x) || dcmp(a[i].y - a[1].y)) return false;
    for (int i = 1; i <= n; i++)
        if (dcmp(b[i].x - a[1].x) || dcmp(b[i].y - a[1].y)) return false;
    return true;
}
int main() {
    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);
    if (isSame()) return puts("1"), 0;
    calcDist();
    floyd();
    int ans = INT_MAX;
    for (int i = 1; i <= m; i++) ans = std::min(ans, dist[i][i]);
    if (ans == INT_MAX) puts("-1");
    else printf("%d\n", ans);
    return 0;
}