Description

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

　　第一行两个整数m和n（m, n ≤ 500），分别表示原材料种数和用户需要的合金种数。第2到m + 1行，每行三
个实数a, b, c（a, b, c ≥ 0 且 a + b + c = 1），分别表示铁铝锡在一种原材料中所占的比重。第m + 2到m +
n + 1行，每行三个实数a, b, c（a, b, c ≥ 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

解题方法：
第三维可以由前两维确定，所以可以无视

两种原料能配成的产品一定在两点间线段

转化成在m个点里找最少点，围成的多边形包括了n个目标点

floyd求最小环。。。

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

否则dis[a][b]=inf

答案是min{dis[i][i]}

特判下所有点重合/共线

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-10
const int inf = 1e8;
void getmin(int &x, int y){
    if(y < x) x = y;
}
struct Point{
    double x, y;
    Point(){}
    Point(double x, double y) : x(x), y(y) {}
}a[505], b[505];
int dis[505][505];
double cross(Point u, Point v){
    return u.x*v.y - u.y*v.x;
}
Point operator -(Point u, Point v){
    return Point(u.x - v.x, u.y - v.y);
}
int n, m;
bool isinline(Point u, Point v){
    if(u.x > v.x) swap(u, v);
    for(int i = 1; i <= m; i++){
        if(b[i].x < u.x || b[i].x > v.x) return false;
    }
    if(u.y > v.y) swap(u, v);
    for(int i = 1; i <= m; i++){
        if(b[i].y < u.y || b[i].y > v.y) return false;
    }
    return 1;
}
int leftorright(Point u, Point v){
    int c1 = 0, c2 = 0;
    for(int i = 1; i <= m; i++){
        double t = cross(v - u, b[i] - u);
        if(t > eps) c1++;
        if(t < -eps) c2++;
        if(c1*c2) return 0;
    }
    if(!c1 && !c2 && isinline(u, v)){
        puts("2");
        return -1;
    }
    if(c1) return 1;
    if(c2) return 2;
    return 3;
}
void floyd(){
    int ans = inf;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dis[j][i] < inf){
                for(int k = 1; k <= n; k++){
                    if(dis[j][k] > dis[j][i] + dis[i][k]){
                        dis[j][k] = dis[j][i] + dis[i][k];
                    }
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        ans = min(ans, dis[i][i]);
    }
    if(ans == inf || ans <= 2)
    {
        puts("-1");
    }
    else{
        printf("%d\n", ans);
    }
}
void getmaze(){
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            int x = leftorright(a[i], a[j]);
            if(x == -1) return;
            else if(x == 1) dis[i][j] = 1;
            else if(x == 2) dis[j][i] = 1;
            else if(x == 3) dis[i][j] = dis[j][i] = 1;
        }
    }
    floyd(); //必须写在这里，不能写在外面，因为返回-1代表不满足了
}
bool pre_judge(){ //判断是否全部重合
    for(int i = 1; i <= n; i++){
        if(fabs(a[i].x - a[1].x) > eps || fabs(a[i].y - a[1].y) > eps) return 0;
    }
    for(int i = 1; i <= m; i++){
        if(fabs(b[i].x - a[1].x) > eps || fabs(b[i].y - a[1].y) > eps) return 0;
    }
    puts("1");
    return 1;
}
int main(){
    memset(dis, 0x3f, sizeof(dis));
    double tmp;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lf%lf%lf", &a[i].x, &a[i].y, &tmp);
    for(int i = 1; i <= m; i++) scanf("%lf%lf%lf", &b[i].x, &b[i].y, &tmp);
    if(pre_judge()){
        return 0;
    }
    getmaze();
    return 0;
}