题目描述
某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的
原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝
锡比重为用户所需要的比重。 现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能
够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。
输入格式
第一行两个整数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），分别表示铁铝锡在一种用户需要的合金中
所占的比重。
输出格式
一个整数，表示最少需要的原材料种数。若无解，则输出–1。
题解
- $a+b+c=1$所以忽略$c$，根据定比分点原则两个点可以表示的点组成它们连线段，推广一下；
- 所以对$n$个点求出凸包，问题即用$m$个点去圈住凸包求最小点数；
- 对两个材料$i,j$，如果凸包上的点都在连线$\vec{ij}$的左边就$i$向$j$连边，$floyd$求所有$dis[i][i]$即可；
- 特判：
- 当凸包是一个点时特判；
- 当凸包是一条直线时，如果叉积为$0$还需要盖住所有点才可以加边，用点积特判；
- bzoj1027
1 #include<bits/stdc++.h> 2 #define db double 3 #define inf 0x3f3f3f3f 4 #define il inline ?5 #define eps 1e-7 6 using namespace std; 7 const int N=510; 8 int n,m,top,dis[N][N]; 9 il int dcmp(db x){return fabs(x)<eps?0:x<0?-1:1;}10 struct poi{11 ????db x,y;12 ????poi(db _x=0,db _y=0):x(_x),y(_y){};13 ????il poi operator -(const poi&A)const{return poi(x-A.x,y-A.y);}14 ????il bool operator <(const poi&A)const{return x==A.x?y<A.y:x<A.x;}15 }p1[N],p2[N],q[N];16 il db crs(poi A,poi B){return A.x*B.y-A.y*B.x;}17 il db dot(poi A,poi B){return A.x*B.x+A.y*B.y;}18 il bool spj(){19 ????int fg=0;20 ????for(int i=2;i<=n;++i)if(dcmp(p1[1].x-p1[i].x)||dcmp(p1[1].y-p1[i].y)){fg=1;break;}21 ????for(int i=1;i<=m;++i)if(dcmp(p1[1].x-p2[i].x)||dcmp(p1[1].y-p2[i].y)){fg=1;break;}22 ????if(!fg){puts("1");return true;}23 ????else return false;24 }25 il void convex(){26 ????sort(p2+1,p2+m+1);27 ????q[top=1]=p2[1];28 ????if(m==1)return;29 ????for(int i=2;i<=m;++i){30 ????????while(top>1&&dcmp(crs(q[top]-q[top-1],p2[i]-q[top]))<=0)top--;31 ????????q[++top]=p2[i];32 ????}33 ????int now=top;34 ????for(int i=m-1;i;--i){35 ????????while(top>now&&dcmp(crs(q[top]-q[top-1],p2[i]-q[top]))<=0)top--;36 ????????q[++top]=p2[i];37 ????}38 ????top--;39 }40 il bool judge(int a,int b){41 ????int i; poi p = p1[b]-p1[a];42 ????for(i=1;i<=top;++i){43 ????????int c = dcmp(crs(p, q[i]-p1[a]));44 ????????if(c>0)break; 45 ????????if(!c&&dcmp(dot(q[i]-p1[b], q[i]-p1[a]))>0)break;46 ????}47 ????return i==top+1?true:false;48 }49 int main(){50 ????#ifndef ONLINE_JUDGE51 ????freopen("bzoj1027.in","r",stdin);52 ????freopen("bzoj1027.out","w",stdout);53 ????#endif 54 ????db tmp;55 ????scanf("%d%d",&n,&m);56 ????for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&p1[i].x,&p1[i].y,&tmp); 57 ????for(int i=1;i<=m;++i)scanf("%lf%lf%lf",&p2[i].x,&p2[i].y,&tmp);58 ????if(spj())return 0;59 ????convex();60 ????memset(dis,0x3f,sizeof(dis));61 ????for(int i=1;i<=n;++i)62 ????for(int j=1;j<=n;++j)if(i!=j){63 ????????if(judge(i,j))dis[i][j]=1;64 ????}65 ????for(int k=1;k<=n;++k)66 ????for(int i=1;i<=n;++i)67 ????for(int j=1;j<=n;++j){68 ????????if(dis[i][j]>dis[i][k]+dis[k][j])69 ????????????dis[i][j] = ?dis[i][k]+dis[k][j];70 ????}71 ????int ans=inf;72 ????for(int i=1;i<=n;++i)ans = min(ans, dis[i][i]);73 ????if(ans==inf)puts("-1"); else printf("%d\n",ans);74 ????return 0;75 }
bzoj1027【JSOI2007】合金
原文地址：https://www.cnblogs.com/Paul-Guderian/p/10269974.html