首页 > 代码库 > BZOJ 1027 合金(凸包-最小环)
BZOJ 1027 合金(凸包-最小环)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1027
题意:三种合金的材料若干种。需求合金若干种。每种需求合金可以由材料合金混合得到。问最少需要多少种材料能够混合出所有需要的合金?
思路:对于两种材料合金ab,若能够得到需 求合金p,那么p必在线段ab上。这里由于三种合金的和为1,只要二维就够了,也就是是一个二维的问题。那么问题转化成,在平面上,找出最少的点包含所有 的需求合金对应的点(答案为1和2特判一下就行)。两两枚举材料合金xy,若所有需求合金对应的点均在xy左侧,则令g[x][y]=1,否则g[x] [y]=INF。然后再g上求最小环就是答案。因为最小环包含了所有需求合金。
struct point { double x,y,z; void get() { RD(x,y,z); } point operator-(point a) { a.x=x-a.x; a.y=y-a.y; return a; } double operator*(point a) { return y*a.x-x*a.y; } double operator^(point a) { return x*a.x+y*a.y; }};point a[N],b[N];int g[N][N],f[N][N],n,m;int sgn(double x){ if(x>EPS) return 1; if(x<-EPS) return -1; return 0;}int OK(point a){ int i; FOR1(i,m) { if(sgn(a.x-b[i].x)||sgn(a.y-b[i].y)) { return 0; } } return 1;}int OK(point p,point q){ int i; FOR1(i,m) { if(sgn((q-p)*(b[i]-p))<0) return 0; } return 1;}int check(point p,point q){ int i; FOR1(i,m) { if(sgn((q-p)*(b[i]-p))!=0) return 0; if(sgn((q-p)^(b[i]-p))<0) return 0; if(sgn((p-q)^(b[i]-q))<0) return 0; } return 1;}int main(){ RD(n,m); int i; FOR1(i,n) a[i].get(); FOR1(i,m) b[i].get(); FOR1(i,n) if(OK(a[i])) { puts("1"); return 0; } int j,k; FOR1(i,n) FOR1(j,n) if(i!=j&&check(a[i],a[j])) { puts("2"); return 0; } FOR1(i,n) FOR1(j,n) { if(i!=j&&OK(a[i],a[j])) { g[i][j]=1; } else g[i][j]=INF; f[i][j]=g[i][j]; } int ans=INF; FOR1(k,n) { FOR1(i,n) if(i!=k) FOR1(j,n) if(i!=j&&k!=j) { ans=min(ans,g[i][j]+f[j][k]+f[k][i]); } FOR1(i,n) FOR1(j,n) { g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } } if(ans==INF) puts("-1"); else PR(ans);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。