「BZOJ1027」[JSOI2007]合金

Description

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

Input

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

Output

一个整数,表示最少需要的原材料种数。若无解,则输出–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

Solution

叉积正负判断顺逆时针,点积正负判断夹角大小。

枚举两个点i,ji,j,若BB点集所有的点都在向量ij\overrightarrow{ij}的左侧或者线段ij\overrightarrow{ij}
对满足条件的(i,j)(i,j)连一条长度为11边,跑最小环。

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
71
72
73
74

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 510;
struct T {
double x, y;
}a[N], b[N];
T operator - (T x, T y) {
return (T) {x.x - y.x, x.y - y.y};
}
double t;
int n, m;
double cross(T x, T y) {
return x.x * y.y - x.y * y.x;
}
double dot(T x, T y) {
return x.x * y.x + x.y * y.y;
}
#define eps 1e-8
int g[N][N];
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&t);
}
for(int i = 1; i <= m; ++i) {
scanf("%lf%lf%lf",&b[i].x,&b[i].y,&t);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) g[i][j] = 1e9;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
bool fg = 1;
for(int k = 1; k <= m; ++k)
if(cross(a[j] - b[k], a[i] - b[k]) > eps || fabs(cross(a[j] - b[k], a[i] - b[k])) < eps && dot(a[j] - b[k], a[i] - b[k]) > eps)
{
fg = 0;
break;
}
if(fg) g[i][j] = 1;
}
}
int ans = 1e9;
for(int k = 1; k <= n; ++k) {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
for(int i = 1; i <= n; ++i) ans = min(ans, g[i][i]);
if(ans == 1e9) {
puts("-1");
return 0;
}
writeln(ans);
return 0;
}