BZOJ1027【JSOI2007】合金 <凸包+Floyed>

Posted on Symbols count in article: 1k Reading time ≈ 4 mins.

Problem

【JSOI2007】合金

Time  Limit:  4  Sec\mathrm{Time\;Limit:\;4\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

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

Input

第一行两个整数mm和nn(m,n≤500)(m,n\le500)，分别表示原材料种数和用户需要的合金种数。第22到m+1m+1行，每行三个实数a,b,c(a,b,c≥0且a+b+c=1)a,b,c(a,b,c\ge0且a+b+c=1)，分别表示铁铝锡在一种原材料中所占的比重。第m+2m+2到m+n+1m+n+1行，每行三个实数a,b,c(a,b,c≥0且a+b+c=1)a,b,c(a,b,c\ge0且a+b+c=1)，分别表示铁铝锡在一种用户需要的合金中所占的比重。

Output

一个整数，表示最少需要的原材料种数。若无解，则输出–1–1。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10 10
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0

Sample Output

1
5

标签：凸包 Floyed

Solution

首先，给出的三个参数确定两个就能确定第三个，因此可以把参数缩减为两个。
考虑两种金属是否能造出第三种金属，若能造成，则第三种金属的两个参数必和这两种金属的参数成比例关系。
推广到用kk种金属制造一种合金，若将这kk种金属的两个参数作为横纵坐标描成点，那么合金所代表的点只要在这kk个点形成的凸包内即可制造。
由此，题目转化为选出尽量少的点使得目标点都在选出点所构成的凸包内。

对于一个条有向线段，它能被选出到凸包上当且仅当所有目标点都在它的左侧。那么处理出所有这样的边后，我们就在点与点间连出了若干条边。我们需要尽量选尽量少的点，即选尽量少的边，使其构成凸包。这样直接跑Floyed\mathrm{Floyed}后枚举起始点即可。

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
#include <bits/stdc++.h>
#define MAX_N 500
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define x first
#define y second
#define mp make_pair
#define pdd pair<dnt,dnt>
using namespace std;
typedef double dnt;
bool G[MAX_N+5][MAX_N+5];
pdd p[MAX_N+5], c[MAX_N+5];
int n, m, f[MAX_N+5][MAX_N+5];
pdd vec(pdd s, pdd t) {return mp(t.x-s.x, t.y-s.y);}
dnt dot(pdd a, pdd b) {return a.x*b.x+a.y*b.y;}
dnt cross(pdd a, pdd b) {return a.x*b.y-a.y*b.x;}
bool chk(pdd s, pdd t, pdd a) {
    dnt mul = cross(vec(a, s), vec(a, t));
    if (fabs(mul) <= EPS && dot(vec(a, s), vec(a, t)) <= EPS) return true; 
    if (mul < -EPS) return true;	return false;
}
bool spj() {
    for (int i = 1; i <= n; i++) if (fabs(p[i].x-p[1].x) > EPS || fabs(p[i].y-p[1].y) > EPS) return false;
    for (int i = 1; i <= m; i++) if (fabs(c[i].x-p[1].x) > EPS || fabs(c[i].y-p[1].y) > EPS) return false;
    return true;
}
int Floyed() {
    int ret = INF;	memset(f, INF, sizeof f);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (G[i][j] && i^j) f[i][j] = 1;
    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
    for (int i = 1; i <= n; i++) ret = min(ret, f[i][i]);
    return spj() ? 1 : (ret == INF ? -1 : ret);
}
int main() {
    scanf("%d%d", &n, &m), memset(G, true, sizeof G);	dnt t;
    for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", &p[i].x, &p[i].y, &t);
    for (int i = 1; i <= m; i++) scanf("%lf%lf%lf", &c[i].x, &c[i].y, &t);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i^j)
        for (int k = 1; k <= m && G[i][j]; k++) G[i][j] &= chk(p[i], p[j], c[k]);
    return printf("%d\n", Floyed()), 0;
}