[BZOJ 1027][JSOI 2007] 合金

题目大意

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

$1 \leqslant n, \; m \leqslant 500$

题目链接

BZOJ 1027

题解

由于三元素百分比之和一定是 $1$ ,所以一种原料或需求可以转化为平面上的点(好神啊)。

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

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

枚举原料点集内的两点 $i$ 、$j$ ,若需求点集内的所有点都在其向量左前方,则令 $dist(i, j) = 1$ ,否则为无穷,最后用 floyd 求一个最小环,$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;
}