Description

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

Input

第 \(1\) 行两个整数 \(m, n\), 分别表示原材料种数和用户需要的合金种数;

第 \(2\) 到 \(m+1\) 行, 每行三个实数 \(a, b, c (a, b, c \geq 0, a + b + c = 1)\), 分别表示铁铝锡在一种原材料中所占的比重;

第 \(m+2\) 到 \(m+n+1\) 行, 每行三个实数 \(a, b, c (a, b, c \geq 0, a + b + c = 1)\), 分别表示铁铝锡在一种用户需要的合金中所占的比重.

Output

一个整数, 表示最少需要的原材料种数. 若无解, 则输出 \(–1\).

Sample Input

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

5

Data Range

对于所有的数据, 保证 \(n, m \leq 500\).

Explanation

题解比较神......

因为第三种合金可以由前两种确定, 所以可以忽略.

现在每种合金都可以由一个二维平面上的点映射而来. 我们考虑任意两种合金 \(a, b\), 若合金 \(c\) 仅由 \(a, b\) 构成, 则 \(c\) 一定在 \(a, b\) 两点的连线上 (这个很显然对不对); 同理, 对于三个点, 由它们构成的合金也在三角形内部. 对应地, 由任意 \(n\) 种合金构成的新合金一定在其凸包内部.

于是, 这个复杂的问题就变成了求一个点集的最小环了......

然后 hzwer 说了些什么我就都没听懂~

floyd 求最小环......

具体就是如果目标点在线段 a, b 的一侧则 \(dis[a][b]=1\)

否则 \(dis[a][b]=\infty\)

答案是 \(min\{dis[i][i]\}\)

特判下所有点重合或共线

反正大概把另一个点集包住就可以了~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 610;
const int infinit = 0x3f3f3f3f;
const llf epsilon = 1e-10;

template <typename _T>
void minimize(_T& a, _T b) {
    if (b < a) a = b; }

struct point {
    llf x, y;
    point(void) {
        x = y = 0.0; }
    point(llf _x, llf _y) {
        x = _x, y = _y; }
}; llf operator * (point a, point b) {
    return a.x * b.y - a.y * b.x;
} point operator - (point a, point b) {
    return point(a.x - b.x, a.y - b.y);
}

class Floyd
{
public:
    point a[maxn], b[maxn];
    int dist[maxn][maxn];
    int n, m;
    bool encapsule(point x, point y)
    {
        if (x.x > y.x)
            swap(x, y);
        for (int i = 1; i <= m; i++)
            if (b[i].x < x.x || b[i].y > y.x)
                return false;
        if (x.y > y.y)
            swap(x, y);
        for (int i = 1; i <= m; i++)
            if (b[i].y < x.y || b[i].y > y.y)
                return false;
        return true;
    }
    int judge(point x, point y)
    {
        int c1 = 0, c2 = 0;
        for (int i = 1; i <= m; i++) {
            llf t = (y - x) * (b[i] - x);
            if (t > epsilon)
                c1 += 1;
            else if (t < -epsilon)
                c2 += 1;
            if (c1 != 0 && c2 != 0)
                return 0;
        }
        if (!c1 && !c2 && encapsule(x, y)) {
            return -1;
        } else if (c1 != 0) {
            return 1;
        } else if (c2 != 0) {
            return 2;
        }
        return 3;
    }
    int floyd(void)
    {
        rep(k, 1, n) rep(i, 1, n)
            if (dist[i][k] < infinit) rep(j, 1, n)
                minimize(dist[i][j], dist[i][k] + dist[k][j]);
        int res = infinit;
        rep(i, 1, n)
            minimize(res, dist[i][i]);
        if (res >= infinit || res <= 2)
            return -1;
        return res;
    }
    bool special_judge(void)
    {
        for (int i = 1; i <= n; i++)
            if (fabs(a[i].x - a[1].x) > epsilon || fabs(a[i].y - a[1].y) > epsilon)
                return false;
        for (int i = 1; i <= m; i++)
            if (fabs(b[i].x - b[1].x) > epsilon || fabs(b[i].y - b[1].y) > epsilon)
                return false;
        return true;
    }
    int eval(void)
    {
        if (special_judge())
            return 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = infinit;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                int t = judge(a[i], a[j]);
                if (t == -1)
                    return 2;
                else if (t == 1)
                    dist[i][j] = 1;
                else if (t == 2)
                    dist[j][i] = 1;
                else if (t == 3)
                    dist[i][j] = dist[j][i] = 1;
            }
        // Running Floyd shortest path
        return floyd();
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    graph.m = m;
    llf _ = 0.0; // Equivalent to /dev/null
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf%lf", &graph.a[i].x, &graph.a[i].y, &_);
    for (int i = 1; i <= m; i++)
        scanf("%lf%lf%lf", &graph.b[i].x, &graph.b[i].y, &_);
    int res = graph.eval();
    printf("%d\n", res);
    return 0;
}