Luogu-4049 [JSOI2007]合金

题目中给出了三种金属的比例，实际上只用考虑两个就可以，第三个可以由另外两个确定qwq

如果把原料和需求看做二维平面上的点，可以发现两种原料能混合成的比例就在他们相连的线段上，也就是说线段上的点都能混合出来。所以如果一种需求包含在一些原料构成的多边形中，他就是可以被混合出来的，题目就变成了用最少的原料点构成的多边形去覆盖所有需求

选出来的点构成的显然是一个凸多边形啊，我们就可以吧那些满足所有需求都在他左/右边的两点连线，然后(floyd)做最小环就好了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+100;
struct Point{
    double x,y;
    Point(double xx=0,double yy=0){
        x=xx,y=yy;
    }
}a[maxn],b[maxn];
struct Vector{
    double x,y;
    Vector(double xx=0,double yy=0){
        x=xx,y=yy;
    }
};
int dcmp(double x){return fabs(x)<1e-9?0:(x>0?1:-1);}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double len(Vector a){return sqrt(a.x*a.x+a.y*a.y);}
int n,m,f[maxn][maxn];
double sb;
void getdist(){
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j){
                int ok=1;
                for(int k=1;k<=m;k++)
                    if(dcmp((a[j]-a[i])*(b[k]-a[i]))<0){
                        ok=0;
                        break;
                    }
                if(ok) f[i][j]=1;
            }
}
void floyd(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(f[j][k]>f[j][i]+f[i][k])
                    f[j][k]=f[j][i]+f[i][k];
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
        ans=min(ans,f[i][i]);
    if(ans==0x3f3f3f3f) printf("-1
");
    else{
        if(ans==2){
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(i!=j){
                        bool ok=1;
                        for(int k=1;k<=m;k++){
                            Vector v1=a[j]-a[i],v2=b[k]-a[i];
                            double x=len(v1),y=len(v2),z=dcmp(v2.x*v1.x);
                            if(y!=0&&(z<0||y>x)){
                                ok=0;
                                break;
                            }
                        }
                        if(ok==1){
                            printf("2
");
                            return;
                        }
                    }
            printf("-1
");
        }
        else printf("%d
",ans);
    }
}
bool tp(){
    for(int i=1;i<m;i++)
        if(dcmp(b[i].x-b[i+1].x)!=0||dcmp(b[i].y-b[i+1].y)!=0)
            return 0;
    for(int i=1;i<=n;i++)
        if(dcmp(a[i].x-b[1].x)==0&&dcmp(a[i].y-b[1].y)==0){
            printf("1
");
            return 1;
        }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&sb);
    for(int i=1;i<=m;i++)
        scanf("%lf%lf%lf",&b[i].x,&b[i].y,&sb);
    if(tp()) return 0;
    getdist();
    floyd();
    return 0;
}